oj.uz

Submission #581314

# Submission time Handle Problem Language Result Execution time Memory
581314 2022-06-22T13:08:52 Z alontanay The short shank; Redemption (BOI21_prison) C++14
15 / 100
 211 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, d, t;
    cin >> n >> d >> t;
    vector<vector<vector<int>>> dp(n+1,vector<vector<int>>(d+1,vector<int>(n+1,1e9)));
    dp[n] = vector<vector<int>>(d+1,vector<int>(n+1,0));
    vector<int> xs(n);
    for(int &x : xs) {
        cin >> x;
    }
    for(int i = n - 1; i >= 0; i --) {
        int x = xs[i];
        if(x > t) {
            for(int e = 0; e <= n; e ++) {
                for(int di = 0; di <= d; di ++) {
                    dp[i][di][e] = dp[i+1][di][e] + (e>i);
                }
            }
        } else {
            int l = (t-x);
            int en = min((i + l),n-1);
            for(int e = 0; e <= n; e ++) {
                dp[i][0][e] = dp[i+1][0][max(e,en+1)] + 1;
            }
            for(int di = 1; di <= d; di ++) {
                for(int e = 0; e <= n; e ++) {
                    dp[i][di][e] = min(dp[i+1][di-1][0],dp[i+1][di][max(e,en+1)]) + 1;
                }
            }
        }
        // for(int di = 0; di <= d; di ++) {
        //     for(int e : dp[i][di]) { cout << e << " "; }
        //     cout << "\n";
        // }
        // cout << "~\n";
    }
    cout << dp[0][d][0];
}

/*
6 2 5
4 6 4 6 4 6
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 8 ms 7764 KB Output is correct
3 Correct 14 ms 14604 KB Output is correct
4 Correct 50 ms 51412 KB Output is correct
5 Correct 96 ms 100460 KB Output is correct
6 Correct 5 ms 4308 KB Output is correct
7 Correct 44 ms 41408 KB Output is correct
8 Correct 12 ms 11348 KB Output is correct
9 Correct 22 ms 21384 KB Output is correct
10 Correct 55 ms 51412 KB Output is correct
11 Correct 99 ms 100496 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 211 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 8 ms 7764 KB Output is correct
3 Correct 14 ms 14604 KB Output is correct
4 Correct 50 ms 51412 KB Output is correct
5 Correct 96 ms 100460 KB Output is correct
6 Correct 5 ms 4308 KB Output is correct
7 Correct 44 ms 41408 KB Output is correct
8 Correct 12 ms 11348 KB Output is correct
9 Correct 22 ms 21384 KB Output is correct
10 Correct 55 ms 51412 KB Output is correct
11 Correct 99 ms 100496 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 8 ms 7856 KB Output is correct
14 Correct 13 ms 14512 KB Output is correct
15 Correct 49 ms 51412 KB Output is correct
16 Correct 97 ms 100416 KB Output is correct
17 Correct 5 ms 4308 KB Output is correct
18 Correct 44 ms 41360 KB Output is correct
19 Correct 13 ms 11348 KB Output is correct
20 Correct 22 ms 21320 KB Output is correct
21 Correct 54 ms 51364 KB Output is correct
22 Correct 102 ms 100436 KB Output is correct
23 Runtime error 211 ms 524288 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Runtime error 203 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 8 ms 7764 KB Output is correct
3 Correct 14 ms 14604 KB Output is correct
4 Correct 50 ms 51412 KB Output is correct
5 Correct 96 ms 100460 KB Output is correct
6 Correct 5 ms 4308 KB Output is correct
7 Correct 44 ms 41408 KB Output is correct
8 Correct 12 ms 11348 KB Output is correct
9 Correct 22 ms 21384 KB Output is correct
10 Correct 55 ms 51412 KB Output is correct
11 Correct 99 ms 100496 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 8 ms 7856 KB Output is correct
14 Correct 13 ms 14512 KB Output is correct
15 Correct 49 ms 51412 KB Output is correct
16 Correct 97 ms 100416 KB Output is correct
17 Correct 5 ms 4308 KB Output is correct
18 Correct 44 ms 41360 KB Output is correct
19 Correct 13 ms 11348 KB Output is correct
20 Correct 22 ms 21320 KB Output is correct
21 Correct 54 ms 51364 KB Output is correct
22 Correct 102 ms 100436 KB Output is correct
23 Runtime error 211 ms 524288 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 8 ms 7764 KB Output is correct
3 Correct 14 ms 14604 KB Output is correct
4 Correct 50 ms 51412 KB Output is correct
5 Correct 96 ms 100460 KB Output is correct
6 Correct 5 ms 4308 KB Output is correct
7 Correct 44 ms 41408 KB Output is correct
8 Correct 12 ms 11348 KB Output is correct
9 Correct 22 ms 21384 KB Output is correct
10 Correct 55 ms 51412 KB Output is correct
11 Correct 99 ms 100496 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Runtime error 211 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -