Submission #887241

#	Time	Username	Problem	Language	Result	Execution time	Memory
887241		_minhduc	The short shank; Redemption (BOI21_prison)	C++14	15 / 100	24 ms	2820 KiB

prison

/**
 *    author:       _minhduc
 *    created:      14-12-2023 13:30:37
**/

#include <bits/stdc++.h>
#define int long long
#define taskname ""

using namespace std;

const int maxN = (int)(1e5);

int n,d,a;
int arr[maxN+5];

namespace sub1 {
    const int N = (int)(500);

    int dp[N+5][N+5];

    void main() {
        for (int i = 0; i < n; i++)
            cin >> arr[i];
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= d+1; j++)
                dp[i][j] = (int)(1e16);
        dp[n][0] = 0;
        for (int i = n-1; i >= 0; i--) 
            for (int j = 1; j <= d+1; j++) {
                int cnt = 0, mn = arr[i];
                for (int k = i+1; k <= n; k++) {
                    cnt += (mn <= a);
                    dp[i][j] = min(dp[i][j],dp[k][j-1] + cnt);
                    mn = min(mn+1,arr[k]);
                }
            }
        cout << dp[0][d+1];
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef LOCAL
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    #ifdef ONLINE_JUDGE
        // freopen(taskname".inp", "r", stdin);
        // freopen(taskname".out", "w", stdout);
    #endif
    cin >> n >> d >> a;
    if (n <= 500)
        sub1::main();
}

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