Submission

Score: 140

User: devilpoohs

Problemset: Chocolate

Language: cpp

Time: 0.066 second

Submitted On: 2026-03-07 12:53:59

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
const int mod=1e9+7;
int n,c,K,l,h;;
int ar[N];
int powi[N];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>K>>c;
    int dp[n+1][K+1];
    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;
    dp[n][0]=1;
    for(int k=1;k<=K;k++){
        dp[n][k]=0;
    }
    for(int i=n-1;i>=0;i--){
        for(int k=0;k<=K;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;
                if(k>=1 and sum>=l){
                    cnt+=dp[j+1][k-1]%mod;
                    cnt%=mod;
                }
            }
            cnt%=mod;
            dp[i][k]=cnt;
        }
    }



    cout<<dp[0][K];
    return 0;
}
/*
8 3 2
7 9 1 3 3 6 2 9
4 64
*/