oj.uz

Submission #890591

# Submission time Handle Problem Language Result Execution time Memory
890591 2023-12-21T14:23:08 Z hafo Collecting Stamps 3 (JOI20_ho_t3) C++14
100 / 100
 108 ms 267388 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 4e2 + 7;
const ll oo = 1e9 + 69;

int n, l, x[maxn], t[maxn], dp[maxn][maxn][207][2];

int add(int a, int b) {
    a += b;
    if(a >= l) a -= l;
    if(a < 0) a += l;
    return a;
}

int dist(int a, int b) {
    return min(add(b, -a), add(a, -b));
}

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

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>l;
    for(int i = 1; i <= n; i++) {
        cin>>x[i];
        x[i + n + 1] = x[i];
    }
    for(int i = 1; i <= n; i++) {
        cin>>t[i];
        t[i + n + 1] = t[i];
    }

    x[1 + n] = 0;
    t[1 + n] = 0;


    int ans = 0;
    for(int i = 0; i <= n * 2 + 1; i++) {
        for(int j = 0; j <= n * 2 + 1; j++) {
            for(int k = 0; k <= n; k++) {
                for(int t = 0; t < 2; t++) dp[i][j][k][t] = oo;
            }
        }
    }

    dp[n + 1][n + 1][0][0] = 0;
    dp[n + 1][n + 1][0][1] = 0;

    for(int i = 2 * n + 1; i >= 1; i--) {
        for(int j = i; j <= 2 * n + 1; j++) {
            if(j - i + 1 >= n + 1 || i > n + 1 || j < n + 1) continue;
            for(int k = 0; k <= n; k++) {
                mini(dp[i][j][k][1], dp[i][j][k][0] + dist(x[j], x[i]));
                mini(dp[i][j][k][0], dp[i][j][k][1] + dist(x[i], x[j]));
                
                int nxt = dp[i][j][k][0];
                if(i - 1 >= 1) {
                    nxt += dist(x[i - 1], x[i]);
                    if(nxt <= t[i - 1] && k + 1 <= n) {
                        mini(dp[i - 1][j][k + 1][0], nxt);
                        maxi(ans, k + 1);
                    }
                    else mini(dp[i - 1][j][k][0], nxt);
                } 

                nxt = dp[i][j][k][1];
                if(j + 1 <= 2 * n + 1) {
                    nxt += dist(x[j + 1], x[j]);
                    if(nxt <= t[j + 1] && k + 1 <= n) {
                        mini(dp[i][j + 1][k + 1][1], nxt);
                        maxi(ans, k + 1);
                    }
                    else mini(dp[i][j + 1][k][1], nxt);
                }
            }
        }
    }

    cout<<ans;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 2 ms 14680 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 2 ms 16984 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 2 ms 16728 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 2 ms 16732 KB Output is correct
13 Correct 2 ms 16732 KB Output is correct
14 Correct 1 ms 10584 KB Output is correct
15 Correct 2 ms 12684 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 2 ms 16732 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 2 ms 14680 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 2 ms 16984 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 2 ms 16728 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 2 ms 16732 KB Output is correct
13 Correct 2 ms 16732 KB Output is correct
14 Correct 1 ms 10584 KB Output is correct
15 Correct 2 ms 12684 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 2 ms 16732 KB Output is correct
18 Correct 3 ms 20828 KB Output is correct
19 Correct 2 ms 14744 KB Output is correct
20 Correct 2 ms 16732 KB Output is correct
21 Correct 2 ms 20828 KB Output is correct
22 Correct 2 ms 14684 KB Output is correct
23 Correct 3 ms 20828 KB Output is correct
24 Correct 2 ms 18780 KB Output is correct
25 Correct 3 ms 20828 KB Output is correct
26 Correct 2 ms 20828 KB Output is correct
27 Correct 2 ms 12636 KB Output is correct
28 Correct 2 ms 14684 KB Output is correct
29 Correct 2 ms 20828 KB Output is correct
30 Correct 2 ms 20824 KB Output is correct
31 Correct 3 ms 20828 KB Output is correct
32 Correct 2 ms 18780 KB Output is correct
33 Correct 2 ms 20824 KB Output is correct
34 Correct 3 ms 20828 KB Output is correct
35 Correct 2 ms 20824 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 2 ms 14680 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 2 ms 16984 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 2 ms 16728 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 2 ms 16732 KB Output is correct
13 Correct 2 ms 16732 KB Output is correct
14 Correct 1 ms 10584 KB Output is correct
15 Correct 2 ms 12684 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 2 ms 16732 KB Output is correct
18 Correct 108 ms 238620 KB Output is correct
19 Correct 44 ms 185172 KB Output is correct
20 Correct 23 ms 136028 KB Output is correct
21 Correct 39 ms 181076 KB Output is correct
22 Correct 51 ms 205652 KB Output is correct
23 Correct 20 ms 125784 KB Output is correct
24 Correct 16 ms 111452 KB Output is correct
25 Correct 19 ms 123552 KB Output is correct
26 Correct 10 ms 76376 KB Output is correct
27 Correct 20 ms 125580 KB Output is correct
28 Correct 18 ms 107100 KB Output is correct
29 Correct 21 ms 127836 KB Output is correct
30 Correct 17 ms 113380 KB Output is correct
31 Correct 19 ms 123740 KB Output is correct
32 Correct 12 ms 88668 KB Output is correct
33 Correct 20 ms 123740 KB Output is correct
34 Correct 9 ms 74332 KB Output is correct
35 Correct 19 ms 121688 KB Output is correct
36 Correct 11 ms 84728 KB Output is correct
37 Correct 20 ms 125540 KB Output is correct
38 Correct 12 ms 92764 KB Output is correct
39 Correct 21 ms 129884 KB Output is correct
40 Correct 14 ms 98904 KB Output is correct
41 Correct 92 ms 265292 KB Output is correct
42 Correct 57 ms 218188 KB Output is correct
43 Correct 88 ms 265300 KB Output is correct
44 Correct 56 ms 215884 KB Output is correct
45 Correct 89 ms 265324 KB Output is correct
46 Correct 55 ms 217936 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 2 ms 14680 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 2 ms 16984 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 2 ms 16728 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 2 ms 16732 KB Output is correct
13 Correct 2 ms 16732 KB Output is correct
14 Correct 1 ms 10584 KB Output is correct
15 Correct 2 ms 12684 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 2 ms 16732 KB Output is correct
18 Correct 3 ms 20828 KB Output is correct
19 Correct 2 ms 14744 KB Output is correct
20 Correct 2 ms 16732 KB Output is correct
21 Correct 2 ms 20828 KB Output is correct
22 Correct 2 ms 14684 KB Output is correct
23 Correct 3 ms 20828 KB Output is correct
24 Correct 2 ms 18780 KB Output is correct
25 Correct 3 ms 20828 KB Output is correct
26 Correct 2 ms 20828 KB Output is correct
27 Correct 2 ms 12636 KB Output is correct
28 Correct 2 ms 14684 KB Output is correct
29 Correct 2 ms 20828 KB Output is correct
30 Correct 2 ms 20824 KB Output is correct
31 Correct 3 ms 20828 KB Output is correct
32 Correct 2 ms 18780 KB Output is correct
33 Correct 2 ms 20824 KB Output is correct
34 Correct 3 ms 20828 KB Output is correct
35 Correct 2 ms 20824 KB Output is correct
36 Correct 108 ms 238620 KB Output is correct
37 Correct 44 ms 185172 KB Output is correct
38 Correct 23 ms 136028 KB Output is correct
39 Correct 39 ms 181076 KB Output is correct
40 Correct 51 ms 205652 KB Output is correct
41 Correct 20 ms 125784 KB Output is correct
42 Correct 16 ms 111452 KB Output is correct
43 Correct 19 ms 123552 KB Output is correct
44 Correct 10 ms 76376 KB Output is correct
45 Correct 20 ms 125580 KB Output is correct
46 Correct 18 ms 107100 KB Output is correct
47 Correct 21 ms 127836 KB Output is correct
48 Correct 17 ms 113380 KB Output is correct
49 Correct 19 ms 123740 KB Output is correct
50 Correct 12 ms 88668 KB Output is correct
51 Correct 20 ms 123740 KB Output is correct
52 Correct 9 ms 74332 KB Output is correct
53 Correct 19 ms 121688 KB Output is correct
54 Correct 11 ms 84728 KB Output is correct
55 Correct 20 ms 125540 KB Output is correct
56 Correct 12 ms 92764 KB Output is correct
57 Correct 21 ms 129884 KB Output is correct
58 Correct 14 ms 98904 KB Output is correct
59 Correct 92 ms 265292 KB Output is correct
60 Correct 57 ms 218188 KB Output is correct
61 Correct 88 ms 265300 KB Output is correct
62 Correct 56 ms 215884 KB Output is correct
63 Correct 89 ms 265324 KB Output is correct
64 Correct 55 ms 217936 KB Output is correct
65 Correct 78 ms 253012 KB Output is correct
66 Correct 70 ms 240468 KB Output is correct
67 Correct 67 ms 236368 KB Output is correct
68 Correct 61 ms 226132 KB Output is correct
69 Correct 77 ms 250960 KB Output is correct
70 Correct 72 ms 244816 KB Output is correct
71 Correct 92 ms 246860 KB Output is correct
72 Correct 74 ms 248968 KB Output is correct
73 Correct 68 ms 238652 KB Output is correct
74 Correct 63 ms 230232 KB Output is correct
75 Correct 71 ms 242516 KB Output is correct
76 Correct 95 ms 259176 KB Output is correct
77 Correct 83 ms 259152 KB Output is correct
78 Correct 63 ms 228176 KB Output is correct
79 Correct 66 ms 232276 KB Output is correct
80 Correct 84 ms 257104 KB Output is correct
81 Correct 65 ms 232276 KB Output is correct
82 Correct 69 ms 240468 KB Output is correct
83 Correct 89 ms 265296 KB Output is correct
84 Correct 72 ms 244624 KB Output is correct
85 Correct 79 ms 255072 KB Output is correct
86 Correct 81 ms 253004 KB Output is correct
87 Correct 70 ms 242620 KB Output is correct
88 Correct 90 ms 267388 KB Output is correct
89 Correct 88 ms 267344 KB Output is correct
90 Correct 75 ms 245080 KB Output is correct
91 Correct 90 ms 267384 KB Output is correct
92 Correct 88 ms 267384 KB Output is correct
93 Correct 86 ms 263248 KB Output is correct