Submission

Score: 0

User: august

Problemset: Chocolate

Language: cpp

Time: 0.035 second

Submitted On: 2026-03-22 19:42:38

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

#define int long long
#define pi pair<int,int>
const int INF = 1e18, N = 5005, MOD = 1e9+7;

int n,k,c,l,r;

int a[N];

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

int fnd(int ind, int partitioned, vector<vector<int>> &dp) {
    if (ind>n) {
        if (partitioned == k) return 1;
        return 0;
    }

    if (dp[ind][partitioned] != -1) return dp[ind][partitioned];

    int sm=0, val=0;
    for (int i=ind; i<=n; i++) {
        val+= pow(i-ind, c)*a[i];
        if (val < l) continue;
        if (val > r) break;
        sm = (sm + fnd(i+1, partitioned+1, dp))%MOD;
    }
    return dp[ind][partitioned] = sm;
}

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<vector<int>> dp(N, vector<int>(N, -1));
    cout<< fnd(1, 0, dp);
}