Submission

PPPPPTPPPP-PPPPP

Score: 140

User: pxsit

Problemset: Chocolate

Language: cpp

Time: 1.088 second

Submitted On: 2025-03-13 15:42:35

/*
    Author : detective conan
    Problem : Chocolate
    created : 13/03/2025 15:03
*/
#include <bits/stdc++.h>
#define FOR(i, s, t) for(int i = s; i <= t; ++i)
#define rep(i, s, t) for(int i = s; i >= t; --i)
#define DB(n, s) cout << n << s
#define ANS(n, s) DB(n, s)
#define mod (int)(1e9 + 7)
#define MAXN (int)5005
#define sum(a, b) ((a%mod) + (b%mod))%mod
#define mul(a, b) ((a%mod) * (b%mod))%mod
#define HAVE_TESTCASE false
#define pb push_back
#define eb emplace_back
#define conan cin.tie(nullptr)->sync_with_stdio(false)

using namespace std;

int A[MAXN], dp[2][MAXN], i2c[MAXN];
// vector<int> sum[MAXN];

void solve() {
    int N, K, c;
    cin >> N >> K >> c;
    FOR(i, 1, N)
        cin >> A[i];
    int L, H;
    cin >> L >> H;
    if (c == 0)
        i2c[0] = 1;
    FOR(i, 1, N)
    {
        i2c[i] = 1;
        FOR(j, 0, c - 1)
        {
            if (1LL * i2c[i] * i > H)
                break;
            i2c[i] *= i;
        }
    }

    // Remove the sum array precomputation

    dp[0][N + 1] = 1;
    FOR(k, 1, K)
    {
        int now = k % 2, nxt = now ^ 1;
        // Clear the current dp row
        FOR(i, 1, N + 1)
        dp[now][i] = 0;

        rep(i, N - k + 1, 1)
        {
            int pl = -1, pr = -1;

            // Calculate sums on-the-fly
            int curr_sum = 0;
            for (int j = i; j <= min(N - k + 1, N); j++)
            {
                // Calculate the sum for subarray from i to j
                if (j == i)
                {
                    curr_sum = i2c[0] * A[j];
                }
                else
                {
                    curr_sum += i2c[j - i] * A[j];
                }

                // Check boundaries
                if (curr_sum > H)
                    break;

                if (curr_sum >= L && curr_sum <= H)
                {
                    if (pl == -1)
                        pl = j;
                    pr = j;
                }
            }

            if (pl != -1 && pr != -1)
                dp[now][i] = (dp[nxt][pr + 1] - dp[nxt][pl] + mod) % mod;
            else
                dp[now][i] = 0;
        }
        FOR(i, 2, N - k + 1)
        dp[now][i] = (dp[now][i] + dp[now][i - 1]) % mod;
    }
    ANS(dp[K % 2][1], '\n');
}

int32_t main() {
    conan;
    int t = 1;
    if (HAVE_TESTCASE) cin >> t;
    while (t--) solve();
}