Submission

xPPPP-PPPPPPPPPP

Score: 140

User: detectives_conan

Problemset: Chocolate

Language: cpp

Time: 0.140 second

Submitted On: 2025-03-13 15:07:17

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int mod = 1e9 + 7;
int n, k, c, L, R;
int arr[2501];
int qs[2501][2501];
int dp[2][2501];

int power(int n, int a){
  if(n==0 && a==0) return 1;
  return pow(n, a);
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> k >> c;
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    cin >> L >> R;
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            qs[i][j] = qs[i][j - 1] + (power(j - i, c) * arr[j]);
            if(qs[i][j] > R) break;
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (qs[1][i] >= L && qs[1][i] <= R) dp[1][i] = 1;
    }
    for (int i = 2; i <= k; ++i) {
        int cur = i&1, pre = cur^1;
        for (int j = 1; j <= n; ++j) {
            dp[cur][j] = 0;
            for (int kk = 1; kk < j; ++kk) {
                if (qs[kk + 1][j] < L || qs[kk + 1][j] > R) continue;
                dp[cur][j] += dp[pre][kk];
                dp[cur][j] %= mod;
            }
        }
    }

    cout << dp[k&1][n];

    return 0;
}