Submission

xxxxxxxxxxxxxxxx

Score: 0

User: PakinDioxide

Problemset: Chocolate

Language: cpp

Time: 0.001 second

Submitted On: 2025-03-13 13:23:08

/*
    author  : PakinDioxide
    created : 13/03/2025 13:05
    task    : c2_su65_chocolate
*/
#include <bits/stdc++.h>
#define ll long long
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

using namespace std;

ll mod = 1e9+7, dp[5005][5005];

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;
    for (auto &e : a) cin >> e;
    cin >> lo >> hi;
    dp[n][0] = 1;
    for (int i = n-1; i >= 0; i--) {
        ll sum = 0;
        for (int j = i; j < n; j++) {
            sum += poww(j-i, c)*a[j];
            if (sum >= lo && sum <= hi) {
                for (int l = 0; l < k; l++) dp[i][l+1] += dp[j+1][l], dp[i][l+1] %= mod;
            }
        }
    }
    cout << dp[0][k] << '\n';
}