Submission #1285938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285938		SamueleVid	The short shank; Redemption (BOI21_prison)	C++20	0 / 100	1 ms	572 KiB

prison

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int N, D, T; cin >> N >> D >> T;
    vector<ll> t(N);
    for (int i = 0; i < N; i ++) cin >> t[i];

    ll dp[N + 1][D + 1][N + 1];
    ll min_value[N + 1][D + 1][N + 1];
    ll best_prev[N + 1][D + 1][N + 1];
    
    for (int n = 0; n <= N; n ++) {
        for (int d = 0; d <= D; d ++) {
            for (int m = 0; m <= N; m ++) {
                dp[n][d][m] = 1e9;
                min_value[n][d][m] = 1e9;
                best_prev[n][d][m] = 1e9;
            }
        }
    }


    for (int d = 0; d <= D; d ++) {
        dp[0][d][0] = 0;
        min_value[0][d][0] = 0;
        best_prev[0][d][0] = 0;
    }
    // min m[0,n-1] dp[n-1,d-1,m]

    for (int n = 1; n <= N; n ++) {
        for (int d = 1; d <= D; d ++) {
            for (int m = 1; m <= n; m ++) {
                if (m < n) {
                    min_value[n][d][m] = min(min_value[n - 1][d][m] + 1, t[n - 1]);
                    dp[n][d][m] = dp[n - 1][d][m] + (min_value[n][d][m] <= T ? 1 : 0);  
                }
                if (m == n) {
                    min_value[n][d][m] = t[n - 1];
                    dp[n][d][m] = best_prev[n - 1][d - 1][m - 1] + (min_value[n][d][m] <= T ? 1 : 0);
                    
                }   
                best_prev[n][d][m] = min(best_prev[n][d][m - 1], dp[n][d][m]);
            }
        }
    }

    ll res = 1e9;
    for (int m = 0; m <= N; m ++) {
        res = min(res, dp[N][D][m]);
    }

    cout << res - 1 << '\n';
}

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