Submission

Score: 80

User: devilpoohs

Problemset: Chocolate

Language: cpp

Time: 1.092 second

Submitted On: 2026-03-07 12:44:04

#include<bits/stdc++.h>
using namespace std;
const int N=5e2+10;
const int mod=1e9+7;
int n,c,K,l,h;;
int ar[N];
int powi[N];
int dp[N][N];
int think(int i,int k){
    if(i==n){
        if(k==0){
            // cout<<'a';
            return 1;
        } 
        return 0;
    }
    if(dp[i][k]!=-1) return dp[i][k]; 
    int cnt=0;
    int sum=0;
    for(int j=i,mul=0;j<n;j++,mul++){
        sum+=(ar[j]*powi[mul]);
        if(sum>h) break;
        // cout<<i<<','<<j<<','<<sum<<'\n';
        if(k>=1 and sum>=l){
            // cout<<j+1<<' '<<k-1;
            cnt+=think(j+1,k-1)%mod;
            cnt%=mod;
        }
    }
    cnt%=mod;
    return dp[i][k]=cnt;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(dp,-1,sizeof(dp));
    cin>>n>>K>>c;
    for(int i=0;i<n;i++){
        cin>>ar[i];
        powi[i]=1;
        for(int j=0;j<c;j++){
            powi[i]*=i;
            powi[i]%=mod;
        }
        // cout<<i<<','<<powi[i]<<'\n';
    }
    cin>>l>>h;
    cout<<think(0,K);
    return 0;
}
/*
8 3 2
7 9 1 3 3 6 2 9
4 64
*/