Submission

Score: 140

User: august

Problemset: Chocolate

Language: cpp

Time: 1.083 second

Submitted On: 2026-03-22 20:27:36

#include <bits/stdc++.h>
using namespace std;

#define pi pair<int,int>
const int N = 5001, MOD = 1e9+7;

int n,k,c,l,r;

int a[N];

int pow(int base, int ex) {
    if (base == 0 && ex == 0) return 1;
    if (base == 1) return 1;

    int ans=1;
    while (ex >= 1) ans *=base,ex--;
    return ans;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin>> n>> k>> c;
    for (int i=1; i<=n; i++) cin>> a[i];
    cin>> l>> r;

    
    vector<int> dp(N,0);
    dp[0] = 1;
    for (int part=1; part<=k; part++) {
        vector<int> ndp(N,0);
        for (int i=0; i<n; i++) {
            if (dp[i] == 0) continue;

            int curval = 0;
            for (int j=i+1; j<=n; j++) {
                int add = pow(j-i-1, c)*a[j];
                curval += add;

                if (curval < l) continue;
                if (curval > r) break;
                ndp[j] = (dp[i] + ndp[j])%MOD; 
            }
        }
        dp = ndp;
    }
    cout<< dp[n];
}