# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
545169 | 2022-04-03T18:02:23 Z | MilosMilutinovic | Collecting Stamps 3 (JOI20_ho_t3) | C++14 | 263 ms | 130772 KB |
#include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; template<typename T> bool chkmin(T&x,T y){return x>y?x=y,1:0;} template<typename T> bool chkmax(T&x,T y){return x<y?x=y,1:0;} int n,k,a[205],t[205]; ll dp[205][205][205][2]; int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) scanf("%d",&t[i]); for(int i=0;i<=n;i++) for(int l=0;l<=n;l++) for(int r=0;r<=n;r++) dp[l][r][i][0]=dp[l][r][i][1]=1e18; dp[0][0][0][0]=dp[0][0][0][1]=0; for(int i=0;i<n;i++) for(int l=0;l<=n;l++) for(int r=0;r<=n;r++) if(l+r<n) for(int st=0;st<2;st++) { { //left ll nt=dp[i][l][r][st]+(st==0?a[l+1]-a[l]:k-a[n+1-r]+a[l+1]); chkmin(dp[i+(nt<=t[l+1])][l+1][r][0],nt); } { //right ll nt=dp[i][l][r][st]+(st==0?a[l]+k-a[n-r]:(a[n+1-r]-a[n-r]+k)%k); chkmin(dp[i+(nt<=t[n-r])][l][r+1][1],nt); } } int ans=0; for(int i=1;i<=n;i++) for(int l=0;l<=n;l++) for(int r=0;r<=n;r++) if(dp[i][l][r][0]!=1e18|dp[i][l][r][1]!=1e18) ans=i; printf("%d",ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 596 KB | Output is correct |
4 | Correct | 1 ms | 468 KB | Output is correct |
5 | Correct | 0 ms | 468 KB | Output is correct |
6 | Correct | 1 ms | 852 KB | Output is correct |
7 | Correct | 0 ms | 468 KB | Output is correct |
8 | Correct | 1 ms | 596 KB | Output is correct |
9 | Correct | 1 ms | 852 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 | 852 KB | Output is correct |
13 | Correct | 1 ms | 852 KB | Output is correct |
14 | Correct | 1 ms | 468 KB | Output is correct |
15 | Correct | 0 ms | 468 KB | Output is correct |
16 | Correct | 1 ms | 852 KB | Output is correct |
17 | Correct | 1 ms | 852 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 596 KB | Output is correct |
4 | Correct | 1 ms | 468 KB | Output is correct |
5 | Correct | 0 ms | 468 KB | Output is correct |
6 | Correct | 1 ms | 852 KB | Output is correct |
7 | Correct | 0 ms | 468 KB | Output is correct |
8 | Correct | 1 ms | 596 KB | Output is correct |
9 | Correct | 1 ms | 852 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 | 852 KB | Output is correct |
13 | Correct | 1 ms | 852 KB | Output is correct |
14 | Correct | 1 ms | 468 KB | Output is correct |
15 | Correct | 0 ms | 468 KB | Output is correct |
16 | Correct | 1 ms | 852 KB | Output is correct |
17 | Correct | 1 ms | 852 KB | Output is correct |
18 | Correct | 1 ms | 980 KB | Output is correct |
19 | Correct | 1 ms | 692 KB | Output is correct |
20 | Correct | 1 ms | 852 KB | Output is correct |
21 | Correct | 1 ms | 952 KB | Output is correct |
22 | Correct | 1 ms | 596 KB | Output is correct |
23 | Correct | 1 ms | 1108 KB | Output is correct |
24 | Correct | 1 ms | 852 KB | Output is correct |
25 | Correct | 1 ms | 948 KB | Output is correct |
26 | Correct | 1 ms | 980 KB | Output is correct |
27 | Correct | 1 ms | 596 KB | Output is correct |
28 | Correct | 1 ms | 596 KB | Output is correct |
29 | Correct | 1 ms | 1108 KB | Output is correct |
30 | Correct | 1 ms | 1108 KB | Output is correct |
31 | Correct | 1 ms | 980 KB | Output is correct |
32 | Correct | 1 ms | 852 KB | Output is correct |
33 | Correct | 1 ms | 1108 KB | Output is correct |
34 | Correct | 1 ms | 1108 KB | Output is correct |
35 | Correct | 1 ms | 1084 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 596 KB | Output is correct |
4 | Correct | 1 ms | 468 KB | Output is correct |
5 | Correct | 0 ms | 468 KB | Output is correct |
6 | Correct | 1 ms | 852 KB | Output is correct |
7 | Correct | 0 ms | 468 KB | Output is correct |
8 | Correct | 1 ms | 596 KB | Output is correct |
9 | Correct | 1 ms | 852 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 | 852 KB | Output is correct |
13 | Correct | 1 ms | 852 KB | Output is correct |
14 | Correct | 1 ms | 468 KB | Output is correct |
15 | Correct | 0 ms | 468 KB | Output is correct |
16 | Correct | 1 ms | 852 KB | Output is correct |
17 | Correct | 1 ms | 852 KB | Output is correct |
18 | Correct | 174 ms | 104920 KB | Output is correct |
19 | Correct | 92 ms | 63656 KB | Output is correct |
20 | Correct | 45 ms | 33892 KB | Output is correct |
21 | Correct | 82 ms | 60012 KB | Output is correct |
22 | Correct | 118 ms | 77924 KB | Output is correct |
23 | Correct | 33 ms | 28908 KB | Output is correct |
24 | Correct | 23 ms | 22632 KB | Output is correct |
25 | Correct | 36 ms | 28204 KB | Output is correct |
26 | Correct | 9 ms | 10836 KB | Output is correct |
27 | Correct | 37 ms | 29540 KB | Output is correct |
28 | Correct | 23 ms | 21056 KB | Output is correct |
29 | Correct | 33 ms | 30156 KB | Output is correct |
30 | Correct | 23 ms | 23688 KB | Output is correct |
31 | Correct | 31 ms | 28244 KB | Output is correct |
32 | Correct | 14 ms | 14804 KB | Output is correct |
33 | Correct | 34 ms | 28272 KB | Output is correct |
34 | Correct | 8 ms | 10068 KB | Output is correct |
35 | Correct | 31 ms | 27712 KB | Output is correct |
36 | Correct | 12 ms | 13140 KB | Output is correct |
37 | Correct | 31 ms | 29500 KB | Output is correct |
38 | Correct | 15 ms | 16212 KB | Output is correct |
39 | Correct | 32 ms | 30656 KB | Output is correct |
40 | Correct | 17 ms | 18048 KB | Output is correct |
41 | Correct | 242 ms | 129492 KB | Output is correct |
42 | Correct | 119 ms | 87120 KB | Output is correct |
43 | Correct | 224 ms | 129440 KB | Output is correct |
44 | Correct | 112 ms | 86092 KB | Output is correct |
45 | Correct | 263 ms | 129564 KB | Output is correct |
46 | Correct | 114 ms | 87184 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 596 KB | Output is correct |
4 | Correct | 1 ms | 468 KB | Output is correct |
5 | Correct | 0 ms | 468 KB | Output is correct |
6 | Correct | 1 ms | 852 KB | Output is correct |
7 | Correct | 0 ms | 468 KB | Output is correct |
8 | Correct | 1 ms | 596 KB | Output is correct |
9 | Correct | 1 ms | 852 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 | 852 KB | Output is correct |
13 | Correct | 1 ms | 852 KB | Output is correct |
14 | Correct | 1 ms | 468 KB | Output is correct |
15 | Correct | 0 ms | 468 KB | Output is correct |
16 | Correct | 1 ms | 852 KB | Output is correct |
17 | Correct | 1 ms | 852 KB | Output is correct |
18 | Correct | 1 ms | 980 KB | Output is correct |
19 | Correct | 1 ms | 692 KB | Output is correct |
20 | Correct | 1 ms | 852 KB | Output is correct |
21 | Correct | 1 ms | 952 KB | Output is correct |
22 | Correct | 1 ms | 596 KB | Output is correct |
23 | Correct | 1 ms | 1108 KB | Output is correct |
24 | Correct | 1 ms | 852 KB | Output is correct |
25 | Correct | 1 ms | 948 KB | Output is correct |
26 | Correct | 1 ms | 980 KB | Output is correct |
27 | Correct | 1 ms | 596 KB | Output is correct |
28 | Correct | 1 ms | 596 KB | Output is correct |
29 | Correct | 1 ms | 1108 KB | Output is correct |
30 | Correct | 1 ms | 1108 KB | Output is correct |
31 | Correct | 1 ms | 980 KB | Output is correct |
32 | Correct | 1 ms | 852 KB | Output is correct |
33 | Correct | 1 ms | 1108 KB | Output is correct |
34 | Correct | 1 ms | 1108 KB | Output is correct |
35 | Correct | 1 ms | 1084 KB | Output is correct |
36 | Correct | 174 ms | 104920 KB | Output is correct |
37 | Correct | 92 ms | 63656 KB | Output is correct |
38 | Correct | 45 ms | 33892 KB | Output is correct |
39 | Correct | 82 ms | 60012 KB | Output is correct |
40 | Correct | 118 ms | 77924 KB | Output is correct |
41 | Correct | 33 ms | 28908 KB | Output is correct |
42 | Correct | 23 ms | 22632 KB | Output is correct |
43 | Correct | 36 ms | 28204 KB | Output is correct |
44 | Correct | 9 ms | 10836 KB | Output is correct |
45 | Correct | 37 ms | 29540 KB | Output is correct |
46 | Correct | 23 ms | 21056 KB | Output is correct |
47 | Correct | 33 ms | 30156 KB | Output is correct |
48 | Correct | 23 ms | 23688 KB | Output is correct |
49 | Correct | 31 ms | 28244 KB | Output is correct |
50 | Correct | 14 ms | 14804 KB | Output is correct |
51 | Correct | 34 ms | 28272 KB | Output is correct |
52 | Correct | 8 ms | 10068 KB | Output is correct |
53 | Correct | 31 ms | 27712 KB | Output is correct |
54 | Correct | 12 ms | 13140 KB | Output is correct |
55 | Correct | 31 ms | 29500 KB | Output is correct |
56 | Correct | 15 ms | 16212 KB | Output is correct |
57 | Correct | 32 ms | 30656 KB | Output is correct |
58 | Correct | 17 ms | 18048 KB | Output is correct |
59 | Correct | 242 ms | 129492 KB | Output is correct |
60 | Correct | 119 ms | 87120 KB | Output is correct |
61 | Correct | 224 ms | 129440 KB | Output is correct |
62 | Correct | 112 ms | 86092 KB | Output is correct |
63 | Correct | 263 ms | 129564 KB | Output is correct |
64 | Correct | 114 ms | 87184 KB | Output is correct |
65 | Correct | 192 ms | 116876 KB | Output is correct |
66 | Correct | 197 ms | 107276 KB | Output is correct |
67 | Correct | 161 ms | 102636 KB | Output is correct |
68 | Correct | 148 ms | 94760 KB | Output is correct |
69 | Correct | 218 ms | 115548 KB | Output is correct |
70 | Correct | 188 ms | 110756 KB | Output is correct |
71 | Correct | 184 ms | 111904 KB | Output is correct |
72 | Correct | 201 ms | 113224 KB | Output is correct |
73 | Correct | 156 ms | 104880 KB | Output is correct |
74 | Correct | 169 ms | 98088 KB | Output is correct |
75 | Correct | 184 ms | 108380 KB | Output is correct |
76 | Correct | 214 ms | 124292 KB | Output is correct |
77 | Correct | 210 ms | 124340 KB | Output is correct |
78 | Correct | 163 ms | 95868 KB | Output is correct |
79 | Correct | 155 ms | 99200 KB | Output is correct |
80 | Correct | 209 ms | 121820 KB | Output is correct |
81 | Correct | 166 ms | 100276 KB | Output is correct |
82 | Correct | 162 ms | 106080 KB | Output is correct |
83 | Correct | 229 ms | 129464 KB | Output is correct |
84 | Correct | 178 ms | 110820 KB | Output is correct |
85 | Correct | 189 ms | 120580 KB | Output is correct |
86 | Correct | 206 ms | 118188 KB | Output is correct |
87 | Correct | 178 ms | 108444 KB | Output is correct |
88 | Correct | 256 ms | 130736 KB | Output is correct |
89 | Correct | 235 ms | 130736 KB | Output is correct |
90 | Correct | 187 ms | 109624 KB | Output is correct |
91 | Correct | 246 ms | 130744 KB | Output is correct |
92 | Correct | 239 ms | 130772 KB | Output is correct |
93 | Correct | 188 ms | 128284 KB | Output is correct |