oj.uz

Submission #758236

# Submission time Handle Problem Language Result Execution time Memory
758236 2023-06-14T09:59:45 Z xyzxyz Collecting Stamps 3 (JOI20_ho_t3) C++14
100 / 100
 1022 ms 455804 KB 
#include<bits/stdc++.h>

#define int long long

using namespace std;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, laenge; cin >> n >> laenge;
    vector<int> wo(n+2, 0), zeit(n+2, 0);
    for(int i=1; i<=n; i++) cin >> wo[i];
    for(int i=1; i<=n; i++) cin >> zeit[i];
    wo[n+1] = laenge;
    zeit[n+1] = 0;
    vector<vector<vector<vector<int>>>> dp(n+2, vector<vector<vector<int>>>(n+2, vector<vector<int>>(n+2, vector<int>(2, 1e18))));
    dp[n+1][0][0][1] = 0;
    dp[n+1][0][0][0] = 0;
    int res = 0;
    for(int c=0; c<n; c++){//Anz Marken
        for(int l=n+1; l>0; l--){//linkes Ende
            for(int r=0; r<l; r++){//rechtes Ende
                if(dp[l][r][c][0]!=1e18){//sind am linken Ende
                    //ans rechte Ende laufen
                    if(r+1!=l){
                        int dist = wo[r+1]+laenge-wo[l];
                        if(dp[l][r][c][0]+dist<=zeit[r+1]){
                            dp[l][r+1][c+1][1] = min(dp[l][r][c][0] + dist, dp[l][r+1][c+1][1]);
                            res = max(res, c+1);
                        }else dp[l][r+1][c][1] = min(dp[l][r+1][c][1], dp[l][r][c][0] + dist);
                    }
                    //ans neue linke Ende laufen
                    if(l-1!=r){
                        int dist = wo[l]-wo[l-1];
                        if(dp[l][r][c][0]+dist<=zeit[l-1]){
                            dp[l-1][r][c+1][0] = min(dp[l-1][r][c+1][0], dp[l][r][c][0] + dist);
                            res = max(res, c+1);
                        }else dp[l-1][r][c][0] = min(dp[l-1][r][c][0], dp[l][r][c][0] + dist);
                    }
                    
                }
                if(dp[l][r][c][1]!=1e18){//sind am rechten Ende
                    //ans linke Ende laufen
                    int dist = wo[r]+laenge-wo[l-1];
                    if(l-1!=r){
                        if(dp[l][r][c][1]+dist<=zeit[l-1]){
                            dp[l-1][r][c+1][0] = min(dp[l-1][r][c+1][0], dp[l][r][c][1] + dist);
                            res = max(res, c+1);
                        }else dp[l-1][r][c][0] = min(dp[l-1][r][c][0], dp[l][r][c][1] + dist);
                    }
                    //ans neue rechte Ende laufen
                    dist = wo[r+1]-wo[r];
                    if(r+1!=l){
                        if(dp[l][r][c][1]+dist<=zeit[r+1]){
                            dp[l][r+1][c+1][1] = min(dp[l][r+1][c+1][1], dp[l][r][c][1] + dist);
                            res = max(res, c+1);
                        }else dp[l][r+1][c][1] = min(dp[l][r+1][c][1], dp[l][r][c][1] + dist);
                    }
                }
            }
        }
    }
    cout << res;
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 443 ms 328064 KB Output is correct
19 Correct 224 ms 155736 KB Output is correct
20 Correct 81 ms 61036 KB Output is correct
21 Correct 186 ms 142832 KB Output is correct
22 Correct 329 ms 210728 KB Output is correct
23 Correct 69 ms 48064 KB Output is correct
24 Correct 49 ms 33352 KB Output is correct
25 Correct 68 ms 46540 KB Output is correct
26 Correct 19 ms 11220 KB Output is correct
27 Correct 71 ms 49568 KB Output is correct
28 Correct 42 ms 30008 KB Output is correct
29 Correct 63 ms 51020 KB Output is correct
30 Correct 47 ms 35788 KB Output is correct
31 Correct 66 ms 46688 KB Output is correct
32 Correct 24 ms 17876 KB Output is correct
33 Correct 66 ms 46528 KB Output is correct
34 Correct 12 ms 10196 KB Output is correct
35 Correct 69 ms 45132 KB Output is correct
36 Correct 20 ms 15064 KB Output is correct
37 Correct 70 ms 49580 KB Output is correct
38 Correct 34 ms 20300 KB Output is correct
39 Correct 68 ms 52788 KB Output is correct
40 Correct 29 ms 23892 KB Output is correct
41 Correct 681 ms 448696 KB Output is correct
42 Correct 380 ms 248780 KB Output is correct
43 Correct 729 ms 448780 KB Output is correct
44 Correct 341 ms 244604 KB Output is correct
45 Correct 1022 ms 448780 KB Output is correct
46 Correct 306 ms 248780 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 356 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 464 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 1 ms 596 KB Output is correct
34 Correct 1 ms 596 KB Output is correct
35 Correct 1 ms 596 KB Output is correct
36 Correct 443 ms 328064 KB Output is correct
37 Correct 224 ms 155736 KB Output is correct
38 Correct 81 ms 61036 KB Output is correct
39 Correct 186 ms 142832 KB Output is correct
40 Correct 329 ms 210728 KB Output is correct
41 Correct 69 ms 48064 KB Output is correct
42 Correct 49 ms 33352 KB Output is correct
43 Correct 68 ms 46540 KB Output is correct
44 Correct 19 ms 11220 KB Output is correct
45 Correct 71 ms 49568 KB Output is correct
46 Correct 42 ms 30008 KB Output is correct
47 Correct 63 ms 51020 KB Output is correct
48 Correct 47 ms 35788 KB Output is correct
49 Correct 66 ms 46688 KB Output is correct
50 Correct 24 ms 17876 KB Output is correct
51 Correct 66 ms 46528 KB Output is correct
52 Correct 12 ms 10196 KB Output is correct
53 Correct 69 ms 45132 KB Output is correct
54 Correct 20 ms 15064 KB Output is correct
55 Correct 70 ms 49580 KB Output is correct
56 Correct 34 ms 20300 KB Output is correct
57 Correct 68 ms 52788 KB Output is correct
58 Correct 29 ms 23892 KB Output is correct
59 Correct 681 ms 448696 KB Output is correct
60 Correct 380 ms 248780 KB Output is correct
61 Correct 729 ms 448780 KB Output is correct
62 Correct 341 ms 244604 KB Output is correct
63 Correct 1022 ms 448780 KB Output is correct
64 Correct 306 ms 248780 KB Output is correct
65 Correct 515 ms 385224 KB Output is correct
66 Correct 461 ms 339016 KB Output is correct
67 Correct 453 ms 317352 KB Output is correct
68 Correct 424 ms 281960 KB Output is correct
69 Correct 503 ms 379628 KB Output is correct
70 Correct 536 ms 356164 KB Output is correct
71 Correct 502 ms 361600 KB Output is correct
72 Correct 580 ms 367792 KB Output is correct
73 Correct 414 ms 328072 KB Output is correct
74 Correct 416 ms 296648 KB Output is correct
75 Correct 496 ms 344852 KB Output is correct
76 Correct 593 ms 422556 KB Output is correct
77 Correct 593 ms 422600 KB Output is correct
78 Correct 423 ms 286604 KB Output is correct
79 Correct 458 ms 302024 KB Output is correct
80 Correct 690 ms 409880 KB Output is correct
81 Correct 438 ms 306872 KB Output is correct
82 Correct 418 ms 333900 KB Output is correct
83 Correct 661 ms 448776 KB Output is correct
84 Correct 517 ms 356168 KB Output is correct
85 Correct 641 ms 403908 KB Output is correct
86 Correct 539 ms 391680 KB Output is correct
87 Correct 461 ms 344864 KB Output is correct
88 Correct 680 ms 455800 KB Output is correct
89 Correct 631 ms 455800 KB Output is correct
90 Correct 432 ms 350216 KB Output is correct
91 Correct 641 ms 455704 KB Output is correct
92 Correct 647 ms 455804 KB Output is correct
93 Correct 566 ms 442368 KB Output is correct