oj.uz

답안 #532381

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
532381 2022-03-02T19:43:55 Z 4fecta The short shank; Redemption (BOI21_prison) C++17
35 / 100
 195 ms 203616 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

const int MN = 4005;

int n, d, T, t[MN], cnt[MN][MN], dp[MN][MN];

void solve(int j, int l, int r, int p1, int p2) {
    int mid = (l + r) >> 1, opt = n + 1;
    for (int i = max(mid, p1); i <= p2; i++) {
        if (dp[mid][j] >= dp[i + 1][j - 1] + cnt[mid][i]) {
            dp[mid][j] = dp[i + 1][j - 1] + cnt[mid][i];
            opt = i;
        }
    }
    if (l == r) return;
    solve(j, mid + 1, r, opt, p2);
    solve(j, l, mid, p1, opt);
}

int32_t main() {
    boost();

    cin >> n >> d >> T;
    for (int i = 1; i <= n; i++) cin >> t[i];
    for (int i = 1; i <= n; i++) {
        int num = 0, mn = 0x3f3f3f3f;
        for (int j = i; j <= n; j++) {
            if (min(mn, t[j]) <= T) num++;
            cnt[i][j] = num;
            mn = min(mn, t[j]) + 1;
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[n + 1][0] = 0;
    for (int i = 1; i <= d + 1; i++) solve(i, 1, n, 1, n);
    printf("%lld\n", dp[1][d + 1]);

    return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 125764 KB Output is correct
2 Correct 47 ms 128152 KB Output is correct
3 Correct 48 ms 128068 KB Output is correct
4 Correct 49 ms 128816 KB Output is correct
5 Correct 50 ms 128836 KB Output is correct
6 Correct 54 ms 128764 KB Output is correct
7 Correct 48 ms 128836 KB Output is correct
8 Correct 48 ms 128788 KB Output is correct
9 Correct 49 ms 128864 KB Output is correct
10 Correct 52 ms 128776 KB Output is correct
11 Correct 49 ms 128784 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 125820 KB Output is correct
2 Runtime error 5 ms 460 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 125764 KB Output is correct
2 Correct 47 ms 128152 KB Output is correct
3 Correct 48 ms 128068 KB Output is correct
4 Correct 49 ms 128816 KB Output is correct
5 Correct 50 ms 128836 KB Output is correct
6 Correct 54 ms 128764 KB Output is correct
7 Correct 48 ms 128836 KB Output is correct
8 Correct 48 ms 128788 KB Output is correct
9 Correct 49 ms 128864 KB Output is correct
10 Correct 52 ms 128776 KB Output is correct
11 Correct 49 ms 128784 KB Output is correct
12 Correct 54 ms 125840 KB Output is correct
13 Correct 51 ms 128068 KB Output is correct
14 Correct 48 ms 128084 KB Output is correct
15 Correct 48 ms 128764 KB Output is correct
16 Correct 51 ms 128772 KB Output is correct
17 Correct 48 ms 128812 KB Output is correct
18 Correct 49 ms 128840 KB Output is correct
19 Correct 48 ms 128764 KB Output is correct
20 Correct 52 ms 128836 KB Output is correct
21 Correct 49 ms 128840 KB Output is correct
22 Correct 49 ms 128864 KB Output is correct
23 Correct 109 ms 203520 KB Output is correct
24 Correct 141 ms 203576 KB Output is correct
25 Correct 152 ms 203528 KB Output is correct
26 Correct 174 ms 203616 KB Output is correct
27 Correct 195 ms 203588 KB Output is correct
28 Correct 99 ms 203528 KB Output is correct
29 Correct 101 ms 203520 KB Output is correct
30 Correct 112 ms 203588 KB Output is correct
31 Correct 138 ms 203520 KB Output is correct
32 Correct 146 ms 203556 KB Output is correct
33 Correct 146 ms 203608 KB Output is correct
34 Correct 101 ms 203572 KB Output is correct
35 Correct 192 ms 203600 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 125804 KB Output is correct
2 Runtime error 4 ms 460 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 125764 KB Output is correct
2 Correct 47 ms 128152 KB Output is correct
3 Correct 48 ms 128068 KB Output is correct
4 Correct 49 ms 128816 KB Output is correct
5 Correct 50 ms 128836 KB Output is correct
6 Correct 54 ms 128764 KB Output is correct
7 Correct 48 ms 128836 KB Output is correct
8 Correct 48 ms 128788 KB Output is correct
9 Correct 49 ms 128864 KB Output is correct
10 Correct 52 ms 128776 KB Output is correct
11 Correct 49 ms 128784 KB Output is correct
12 Correct 54 ms 125840 KB Output is correct
13 Correct 51 ms 128068 KB Output is correct
14 Correct 48 ms 128084 KB Output is correct
15 Correct 48 ms 128764 KB Output is correct
16 Correct 51 ms 128772 KB Output is correct
17 Correct 48 ms 128812 KB Output is correct
18 Correct 49 ms 128840 KB Output is correct
19 Correct 48 ms 128764 KB Output is correct
20 Correct 52 ms 128836 KB Output is correct
21 Correct 49 ms 128840 KB Output is correct
22 Correct 49 ms 128864 KB Output is correct
23 Correct 109 ms 203520 KB Output is correct
24 Correct 141 ms 203576 KB Output is correct
25 Correct 152 ms 203528 KB Output is correct
26 Correct 174 ms 203616 KB Output is correct
27 Correct 195 ms 203588 KB Output is correct
28 Correct 99 ms 203528 KB Output is correct
29 Correct 101 ms 203520 KB Output is correct
30 Correct 112 ms 203588 KB Output is correct
31 Correct 138 ms 203520 KB Output is correct
32 Correct 146 ms 203556 KB Output is correct
33 Correct 146 ms 203608 KB Output is correct
34 Correct 101 ms 203572 KB Output is correct
35 Correct 192 ms 203600 KB Output is correct
36 Correct 49 ms 125804 KB Output is correct
37 Runtime error 4 ms 460 KB Execution killed with signal 11
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 125764 KB Output is correct
2 Correct 47 ms 128152 KB Output is correct
3 Correct 48 ms 128068 KB Output is correct
4 Correct 49 ms 128816 KB Output is correct
5 Correct 50 ms 128836 KB Output is correct
6 Correct 54 ms 128764 KB Output is correct
7 Correct 48 ms 128836 KB Output is correct
8 Correct 48 ms 128788 KB Output is correct
9 Correct 49 ms 128864 KB Output is correct
10 Correct 52 ms 128776 KB Output is correct
11 Correct 49 ms 128784 KB Output is correct
12 Correct 46 ms 125820 KB Output is correct
13 Runtime error 5 ms 460 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -