Submission

Score: 160

User: syndrxme

Problemset: Chocolate

Language: cpp

Time: 0.077 second

Submitted On: 2026-03-14 14:40:33

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1000000007;

int main() {
    // โหมด Fast I/O เพิ่มความเร็ว
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k_parts, c;
    if (!(cin >> n >> k_parts >> c)) return 0;

    vector<long long> A(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
    }

    long long L, H;
    cin >> L >> H;

    // 1. คำนวณเลขยกกำลังล่วงหน้า (Precompute Powers)
    // ระวังเงื่อนไข 0^0 = 1 
    vector<long long> P(n + 1, 0);
    P[0] = (c == 0) ? 1 : 0; 
    for (int i = 1; i <= n; i++) {
        long long p = 1;
        for (int j = 0; j < c; j++) {
            p *= i;
            if (p > H) { p = H + 1; break; } // กันตัวเลขล้น (Overflow)
        }
        P[i] = p;
    }

    // 2. หาช่วงรอยตัดที่ถูกต้อง [left_j, right_j] สำหรับแต่ละจุดสิ้นสุด i
    vector<int> left_j(n + 1, n + 1);
    vector<int> right_j(n + 1, -1);

    for (int j = 0; j < n; j++) { // j คือจุดที่ถูกตัดก่อนหน้า (รอยต่อ)
        long long cost = 0;
        for (int i = j + 1; i <= n; i++) { // i คือช่องที่เรากำลังจะพิจารณา
            long long power = P[i - j - 1];
            if (power > H) break; // ถ้าแค่ตัวคูณก็เกิน H แล้ว ให้ข้ามเลย
            
            long long term = power * A[i];
            if (term > H || cost + term > H) break; // ถ้ารวมแล้วเกิน H ก็ไม่ต้องลาก i ต่อแล้ว
            
            cost += term;

            if (cost >= L) { // ถ้ามูลค่าอยู่ในช่วง [L, H] จดรอยตัด j เอาไว้
                left_j[i] = min(left_j[i], j);
                right_j[i] = max(right_j[i], j);
            }
        }
    }

    // 3. เริ่มทำ Dynamic Programming
    vector<long long> dp(n + 1, 0);
    dp[0] = 1; // Base case: ช็อกโกแลต 0 ชิ้น แบ่งเป็น 0 ส่วน ได้ 1 วิธี

    for (int k = 1; k <= k_parts; k++) { // ลูปแบ่งทีละรอบ จนครบ k_parts ส่วน
        vector<long long> next_dp(n + 1, 0);
        vector<long long> pref(n + 1, 0); // Prefix Sum ของ DP รอบที่แล้ว
        
        pref[0] = dp[0];
        for (int i = 1; i <= n; i++) {
            pref[i] = (pref[i - 1] + dp[i]) % MOD;
        }

        for (int i = 1; i <= n; i++) {
            // ถ้ารอยตัดซ้าย-ขวาถูกต้อง (มีคำตอบ)
            if (left_j[i] <= right_j[i]) {
                long long sum = pref[right_j[i]];
                if (left_j[i] > 0) {
                    // การลบด้วย Modulo ต้องระวังค่าติดลบ จึงต้อง + MOD เข้าไปก่อน
                    sum = (sum - pref[left_j[i] - 1] + MOD) % MOD;
                }
                next_dp[i] = sum;
            }
        }
        dp = next_dp; // อัปเดตคำตอบเพื่อใช้ในรอบถัดไป
    }

    // พิมพ์คำตอบของช่องสุดท้าย (n) หลังแบ่งครบ K ส่วน
    cout << dp[n] << "\n";

    return 0;
}