Submission #847300

#	Time	Username	Problem	Language	Result	Execution time	Memory
847300		MinaRagy06	The short shank; Redemption (BOI21_prison)	C++17	35 / 100	2087 ms	8660 KiB

prison

#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;

int n, m, t;
int a[2'000'005];
array<int, 2> dp[2'000'005];
array<int, 2> calc(int c) {
    for (int i = 0; i < n; i++) {
        dp[i] = {int(1e9), int(1e9)};
    }
    dp[n] = {0, 0};
    for (int i = n - 1; i >= 0; i--) {
        int cur = 1e9, ctr = 0;
        for (int k = i; k < n; k++) {
            cur = min(cur + 1, a[k]);
            ctr += (cur <= t);
            dp[i] = min(dp[i], {dp[k + 1][0] + ctr, dp[k + 1][1]});
        }
        dp[i][0] += c, dp[i][1]++;
    }
    return {dp[0][0], dp[0][1]};
}
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> t;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    m++;
    int l = 0, r = n;
    while (l <= r) {
        int md = (l + r) >> 1;
        array<int, 2> v = calc(md);
        if (v[1] <= m) {
            r = md - 1;
        } else {
            l = md + 1;
        }
    }
    cout << calc(l)[0] - m * l << '\n';
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 10
• Subtask 3: 20 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20