oj.uz

Submission #669490

# Submission time Handle Problem Language Result Execution time Memory
669490 2022-12-06T14:43:46 Z GrandTiger1729 Collecting Stamps 3 (JOI20_ho_t3) C++17
100 / 100
 162 ms 126148 KB 
#include <iostream>
using namespace std;

const long long INF = 1e18;
int main(){
    int n;
    long long L;
    cin >> n >> L;
    long long a[n], b[n];
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    for (int i = 0; i < n; i++){
        cin >> b[i];
    }
    auto idx = [&](int i) -> int {
        return (i % n + n) % n;
    };
    auto dis = [&](long long x, long long y) -> long long {
        if (x > y) swap(x, y);
        return min(y - x, x + L - y);
    };
    long long dp[n][n][n + 1][2]{}; // [l, r], pickcnt, cur(l, r) => min time
    fill_n(&dp[0][0][0][0], sizeof(dp) / sizeof(long long), INF);
    for (int i = 0; i < n; i++){
        dp[i][i][min(a[i], L - a[i]) <= b[i]][0] = dp[i][i][min(a[i], L - a[i]) <= b[i]][1] = min(a[i], L - a[i]);
    }
    for (int t = 0; t < n - 1; t++){
        for (int l = n - 1; l >= 0; l--){
            int r = idx(l + t);
            for (int i = 0; i < n; i++){
                if (dp[l][r][i][0] + dis(a[l], a[idx(l - 1)]) <= b[idx(l - 1)])
                    dp[idx(l - 1)][r][i + 1][0] = min(dp[idx(l - 1)][r][i + 1][0], dp[l][r][i][0] + dis(a[l], a[idx(l - 1)]));
                if (dp[l][r][i][1] + dis(a[r], a[idx(l - 1)]) <= b[idx(l - 1)])
                    dp[idx(l - 1)][r][i + 1][0] = min(dp[idx(l - 1)][r][i + 1][0], dp[l][r][i][1] + dis(a[r], a[idx(l - 1)]));
                if (dp[l][r][i][0] + dis(a[l], a[idx(r + 1)]) <= b[idx(r + 1)])
                    dp[l][idx(r + 1)][i + 1][1] = min(dp[l][idx(r + 1)][i + 1][1], dp[l][r][i][0] + dis(a[l], a[idx(r + 1)]));
                if (dp[l][r][i][1] + dis(a[r], a[idx(r + 1)]) <= b[idx(r + 1)])
                    dp[l][idx(r + 1)][i + 1][1] = min(dp[l][idx(r + 1)][i + 1][1], dp[l][r][i][1] + dis(a[r], a[idx(r + 1)]));
            }
            for (int i = 0; i <= n; i++){
                dp[idx(l - 1)][r][i][0] = min(dp[idx(l - 1)][r][i][0], dp[l][r][i][0] + dis(a[l], a[idx(l - 1)]));
                dp[idx(l - 1)][r][i][0] = min(dp[idx(l - 1)][r][i][0], dp[l][r][i][1] + dis(a[r], a[idx(l - 1)]));
                dp[l][idx(r + 1)][i][1] = min(dp[l][idx(r + 1)][i][1], dp[l][r][i][0] + dis(a[l], a[idx(r + 1)]));
                dp[l][idx(r + 1)][i][1] = min(dp[l][idx(r + 1)][i][1], dp[l][r][i][1] + dis(a[r], a[idx(r + 1)]));
            }
        }
    }
    for (int i = n; i >= 0; i--){
        for (int j = 0; j < n; j++){
            if (dp[j][idx(j + n - 1)][i][0] != INF || dp[j][idx(j + n - 1)][i][1] != INF){
                cout << i;
                return 0;
            }
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 1 ms 296 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 296 KB Output is correct
24 Correct 1 ms 300 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 300 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 0 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 300 KB Output is correct
35 Correct 0 ms 340 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 95 ms 90620 KB Output is correct
19 Correct 55 ms 42580 KB Output is correct
20 Correct 22 ms 16576 KB Output is correct
21 Correct 40 ms 39080 KB Output is correct
22 Correct 58 ms 57784 KB Output is correct
23 Correct 13 ms 13012 KB Output is correct
24 Correct 9 ms 9036 KB Output is correct
25 Correct 14 ms 12580 KB Output is correct
26 Correct 3 ms 2984 KB Output is correct
27 Correct 15 ms 13340 KB Output is correct
28 Correct 9 ms 8020 KB Output is correct
29 Correct 20 ms 13780 KB Output is correct
30 Correct 13 ms 9684 KB Output is correct
31 Correct 14 ms 12616 KB Output is correct
32 Correct 6 ms 4820 KB Output is correct
33 Correct 13 ms 12500 KB Output is correct
34 Correct 3 ms 2772 KB Output is correct
35 Correct 12 ms 12116 KB Output is correct
36 Correct 5 ms 4008 KB Output is correct
37 Correct 15 ms 13372 KB Output is correct
38 Correct 5 ms 5460 KB Output is correct
39 Correct 16 ms 14292 KB Output is correct
40 Correct 6 ms 6448 KB Output is correct
41 Correct 125 ms 124272 KB Output is correct
42 Correct 75 ms 68492 KB Output is correct
43 Correct 127 ms 124284 KB Output is correct
44 Correct 73 ms 67156 KB Output is correct
45 Correct 135 ms 124272 KB Output is correct
46 Correct 73 ms 68456 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 1 ms 296 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 296 KB Output is correct
24 Correct 1 ms 300 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 300 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 0 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 300 KB Output is correct
35 Correct 0 ms 340 KB Output is correct
36 Correct 95 ms 90620 KB Output is correct
37 Correct 55 ms 42580 KB Output is correct
38 Correct 22 ms 16576 KB Output is correct
39 Correct 40 ms 39080 KB Output is correct
40 Correct 58 ms 57784 KB Output is correct
41 Correct 13 ms 13012 KB Output is correct
42 Correct 9 ms 9036 KB Output is correct
43 Correct 14 ms 12580 KB Output is correct
44 Correct 3 ms 2984 KB Output is correct
45 Correct 15 ms 13340 KB Output is correct
46 Correct 9 ms 8020 KB Output is correct
47 Correct 20 ms 13780 KB Output is correct
48 Correct 13 ms 9684 KB Output is correct
49 Correct 14 ms 12616 KB Output is correct
50 Correct 6 ms 4820 KB Output is correct
51 Correct 13 ms 12500 KB Output is correct
52 Correct 3 ms 2772 KB Output is correct
53 Correct 12 ms 12116 KB Output is correct
54 Correct 5 ms 4008 KB Output is correct
55 Correct 15 ms 13372 KB Output is correct
56 Correct 5 ms 5460 KB Output is correct
57 Correct 16 ms 14292 KB Output is correct
58 Correct 6 ms 6448 KB Output is correct
59 Correct 125 ms 124272 KB Output is correct
60 Correct 75 ms 68492 KB Output is correct
61 Correct 127 ms 124284 KB Output is correct
62 Correct 73 ms 67156 KB Output is correct
63 Correct 135 ms 124272 KB Output is correct
64 Correct 73 ms 68456 KB Output is correct
65 Correct 118 ms 106540 KB Output is correct
66 Correct 105 ms 93576 KB Output is correct
67 Correct 91 ms 87508 KB Output is correct
68 Correct 76 ms 77648 KB Output is correct
69 Correct 113 ms 104852 KB Output is correct
70 Correct 103 ms 98248 KB Output is correct
71 Correct 100 ms 99912 KB Output is correct
72 Correct 104 ms 101516 KB Output is correct
73 Correct 94 ms 90572 KB Output is correct
74 Correct 87 ms 81808 KB Output is correct
75 Correct 104 ms 95176 KB Output is correct
76 Correct 113 ms 116956 KB Output is correct
77 Correct 117 ms 116960 KB Output is correct
78 Correct 89 ms 78960 KB Output is correct
79 Correct 87 ms 83224 KB Output is correct
80 Correct 130 ms 113412 KB Output is correct
81 Correct 90 ms 84656 KB Output is correct
82 Correct 133 ms 92032 KB Output is correct
83 Correct 149 ms 124176 KB Output is correct
84 Correct 106 ms 98340 KB Output is correct
85 Correct 148 ms 111660 KB Output is correct
86 Correct 117 ms 108108 KB Output is correct
87 Correct 101 ms 95172 KB Output is correct
88 Correct 135 ms 126148 KB Output is correct
89 Correct 156 ms 126148 KB Output is correct
90 Correct 102 ms 96748 KB Output is correct
91 Correct 162 ms 126032 KB Output is correct
92 Correct 158 ms 126068 KB Output is correct
93 Correct 143 ms 122404 KB Output is correct