Submission

xPPPPx-------P--

Score: 50

User: PakinDioxide

Problemset: Chocolate

Language: cpp

Time: 0.056 second

Submitted On: 2025-03-13 15:37:32

/*
    author  : PakinDioxide
    created : 13/03/2025 13:05
    task    : c2_su65_chocolate
*/
#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll mod = 1e9+7;

ll poww(ll x, ll y) {
    if (y == 0) return 1;
    ll k = poww(x, y/2);
    k *= k;
    if (y & 1LL) k *= x;
    return k;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, k, c;
    cin >> n >> k >> c;
    ll a[n], lo, hi, dp[n+5][k+5], pdp[n+5][n+5];
    memset(dp, 0, sizeof(dp));
    memset(pdp, 0, sizeof(pdp));
    for (auto &e : a) cin >> e;
    cin >> lo >> hi;
    dp[n][0] = 1;
    for (int i = 0; i < n; i++) {
        pdp[i][i] = poww(0, c)*a[i];
        for (int j = i+1; j < n; j++) pdp[i][j] = pdp[i][j-1] + poww(j-i, c) * a[j];
    }
    for (int i = n-1; i >= 0; i--) {
        ll idx1 = lower_bound(pdp[i]+i, pdp[i]+n, lo) - pdp[i];
        ll idx2 = upper_bound(pdp[i]+i, pdp[i]+n, hi) - pdp[i] - 1;
        for (int l = 0; l <= k; l++) dp[i][l] += dp[i+1][l];
        if (idx1 > idx2) continue;
        for (int l = 0; l < k; l++) dp[i][l+1] += (dp[idx1+1][l] - dp[idx2+2][l]);
    }
    cout << dp[0][k]-dp[1][k] << '\n';
}