# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
329824 | 2020-11-22T17:53:35 Z | TLP39 | Solar Storm (NOI20_solarstorm) | C++14 | 435 ms | 118620 KB |
#include<bits/stdc++.h> using namespace std; int main() { int n,s; long long int k; scanf("%d %d %lld",&n,&s,&k); int d[n+1]={}; int v[n]={}; for(int i=1;i<n;i++) { scanf("%d",&d[i]); } for(int i=0;i<n;i++) { scanf("%d",&v[i]); } int ma[n]={}; int po=0,pr=0; long long int sum=0; while(po<n || pr<n) { if(po==n) { ma[pr]=n-1; pr++; } else if(sum<=k) { po++; sum+=(long long)1*d[po]; } else { ma[pr]=po-1; pr++; sum-=(long long)1*d[pr]; } } int di[30]={}; int pp=0; int temp=s; while(temp>0) { di[pp]=temp; pp++; temp=temp/2; } sort(di,di+pp); int res[pp][n]; memset(res,0,sizeof res); for(int i=0;i<n;i++) { res[0][i]=ma[ma[i]]; } for(int i=1;i<pp;i++) { for(int j=0;j<n;j++) { if(di[i]%2==0) { if(res[i-1][j]==n-1) { res[i][j]=n-1; } else { res[i][j]=res[i-1][res[i-1][j]+1]; } } else { if(res[i-1][j]==n-1) { res[i][j]=n-1; } else { res[i][j]=res[i-1][res[i-1][j]+1]; if(res[i][j]!=n-1) { res[i][j]=res[0][res[i][j]+1]; } } } } } long long int val[n+1]; int be; val[0]=0; for(int i=1;i<=n;i++) { val[i]=val[i-1]+(long long)1*v[i-1]; } long long int maxx=0,hol; for(int i=0;i<n;i++) { hol=val[res[pp-1][i]+1]-val[i]; if(hol>maxx) { maxx=hol; be=i; } } printf("%d\n",s); for(int i=0;i<s;i++) { printf("%d ",ma[be]+1); be=res[0][be]+1; if(be>=n) { be=n-1; } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 492 KB | Output is correct |
2 | Correct | 3 ms | 620 KB | Output is correct |
3 | Correct | 3 ms | 620 KB | Output is correct |
4 | Correct | 2 ms | 492 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 2 ms | 620 KB | Output is correct |
7 | Correct | 3 ms | 620 KB | Output is correct |
8 | Correct | 3 ms | 620 KB | Output is correct |
9 | Correct | 3 ms | 640 KB | Output is correct |
10 | Correct | 3 ms | 620 KB | Output is correct |
11 | Correct | 3 ms | 620 KB | Output is correct |
12 | Correct | 2 ms | 492 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 187 ms | 27884 KB | Output is correct |
2 | Correct | 118 ms | 17900 KB | Output is correct |
3 | Correct | 133 ms | 19180 KB | Output is correct |
4 | Correct | 142 ms | 20844 KB | Output is correct |
5 | Correct | 165 ms | 24428 KB | Output is correct |
6 | Correct | 221 ms | 32492 KB | Output is correct |
7 | Correct | 146 ms | 21484 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 492 KB | Output is correct |
2 | Correct | 3 ms | 620 KB | Output is correct |
3 | Correct | 3 ms | 620 KB | Output is correct |
4 | Correct | 2 ms | 492 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 2 ms | 620 KB | Output is correct |
7 | Correct | 3 ms | 620 KB | Output is correct |
8 | Correct | 3 ms | 620 KB | Output is correct |
9 | Correct | 3 ms | 640 KB | Output is correct |
10 | Correct | 3 ms | 620 KB | Output is correct |
11 | Correct | 3 ms | 620 KB | Output is correct |
12 | Correct | 2 ms | 492 KB | Output is correct |
13 | Correct | 187 ms | 27884 KB | Output is correct |
14 | Correct | 118 ms | 17900 KB | Output is correct |
15 | Correct | 133 ms | 19180 KB | Output is correct |
16 | Correct | 142 ms | 20844 KB | Output is correct |
17 | Correct | 165 ms | 24428 KB | Output is correct |
18 | Correct | 221 ms | 32492 KB | Output is correct |
19 | Correct | 146 ms | 21484 KB | Output is correct |
20 | Correct | 136 ms | 20588 KB | Output is correct |
21 | Correct | 174 ms | 25068 KB | Output is correct |
22 | Correct | 222 ms | 29696 KB | Output is correct |
23 | Correct | 187 ms | 28268 KB | Output is correct |
24 | Correct | 185 ms | 27628 KB | Output is correct |
25 | Correct | 192 ms | 27628 KB | Output is correct |
26 | Correct | 191 ms | 20588 KB | Output is correct |
27 | Correct | 180 ms | 26348 KB | Output is correct |
28 | Correct | 189 ms | 26112 KB | Output is correct |
29 | Correct | 276 ms | 33900 KB | Output is correct |
30 | Correct | 190 ms | 27756 KB | Output is correct |
31 | Correct | 164 ms | 24556 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 317 ms | 89452 KB | Output is correct |
2 | Correct | 140 ms | 44396 KB | Output is correct |
3 | Correct | 138 ms | 39148 KB | Output is correct |
4 | Correct | 195 ms | 50284 KB | Output is correct |
5 | Correct | 177 ms | 36972 KB | Output is correct |
6 | Correct | 185 ms | 29548 KB | Output is correct |
7 | Correct | 347 ms | 106604 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 492 KB | Output is correct |
2 | Correct | 3 ms | 620 KB | Output is correct |
3 | Correct | 3 ms | 620 KB | Output is correct |
4 | Correct | 2 ms | 492 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 2 ms | 620 KB | Output is correct |
7 | Correct | 3 ms | 620 KB | Output is correct |
8 | Correct | 3 ms | 620 KB | Output is correct |
9 | Correct | 3 ms | 640 KB | Output is correct |
10 | Correct | 3 ms | 620 KB | Output is correct |
11 | Correct | 3 ms | 620 KB | Output is correct |
12 | Correct | 2 ms | 492 KB | Output is correct |
13 | Correct | 4 ms | 1132 KB | Output is correct |
14 | Correct | 3 ms | 748 KB | Output is correct |
15 | Correct | 3 ms | 748 KB | Output is correct |
16 | Correct | 2 ms | 620 KB | Output is correct |
17 | Correct | 3 ms | 748 KB | Output is correct |
18 | Correct | 3 ms | 748 KB | Output is correct |
19 | Correct | 3 ms | 748 KB | Output is correct |
20 | Correct | 2 ms | 748 KB | Output is correct |
21 | Correct | 5 ms | 1260 KB | Output is correct |
22 | Correct | 4 ms | 1004 KB | Output is correct |
23 | Correct | 4 ms | 1144 KB | Output is correct |
24 | Correct | 4 ms | 1132 KB | Output is correct |
25 | Correct | 4 ms | 1132 KB | Output is correct |
26 | Correct | 3 ms | 1004 KB | Output is correct |
27 | Correct | 3 ms | 876 KB | Output is correct |
28 | Correct | 3 ms | 876 KB | Output is correct |
29 | Correct | 3 ms | 1004 KB | Output is correct |
30 | Correct | 3 ms | 748 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 492 KB | Output is correct |
2 | Correct | 3 ms | 620 KB | Output is correct |
3 | Correct | 3 ms | 620 KB | Output is correct |
4 | Correct | 2 ms | 492 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 2 ms | 620 KB | Output is correct |
7 | Correct | 3 ms | 620 KB | Output is correct |
8 | Correct | 3 ms | 620 KB | Output is correct |
9 | Correct | 3 ms | 640 KB | Output is correct |
10 | Correct | 3 ms | 620 KB | Output is correct |
11 | Correct | 3 ms | 620 KB | Output is correct |
12 | Correct | 2 ms | 492 KB | Output is correct |
13 | Correct | 187 ms | 27884 KB | Output is correct |
14 | Correct | 118 ms | 17900 KB | Output is correct |
15 | Correct | 133 ms | 19180 KB | Output is correct |
16 | Correct | 142 ms | 20844 KB | Output is correct |
17 | Correct | 165 ms | 24428 KB | Output is correct |
18 | Correct | 221 ms | 32492 KB | Output is correct |
19 | Correct | 146 ms | 21484 KB | Output is correct |
20 | Correct | 136 ms | 20588 KB | Output is correct |
21 | Correct | 174 ms | 25068 KB | Output is correct |
22 | Correct | 222 ms | 29696 KB | Output is correct |
23 | Correct | 187 ms | 28268 KB | Output is correct |
24 | Correct | 185 ms | 27628 KB | Output is correct |
25 | Correct | 192 ms | 27628 KB | Output is correct |
26 | Correct | 191 ms | 20588 KB | Output is correct |
27 | Correct | 180 ms | 26348 KB | Output is correct |
28 | Correct | 189 ms | 26112 KB | Output is correct |
29 | Correct | 276 ms | 33900 KB | Output is correct |
30 | Correct | 190 ms | 27756 KB | Output is correct |
31 | Correct | 164 ms | 24556 KB | Output is correct |
32 | Correct | 233 ms | 46188 KB | Output is correct |
33 | Correct | 186 ms | 37996 KB | Output is correct |
34 | Correct | 255 ms | 52344 KB | Output is correct |
35 | Correct | 152 ms | 31596 KB | Output is correct |
36 | Correct | 164 ms | 33772 KB | Output is correct |
37 | Correct | 179 ms | 34668 KB | Output is correct |
38 | Correct | 270 ms | 56556 KB | Output is correct |
39 | Correct | 212 ms | 39532 KB | Output is correct |
40 | Correct | 271 ms | 56940 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 492 KB | Output is correct |
2 | Correct | 3 ms | 620 KB | Output is correct |
3 | Correct | 3 ms | 620 KB | Output is correct |
4 | Correct | 2 ms | 492 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 2 ms | 620 KB | Output is correct |
7 | Correct | 3 ms | 620 KB | Output is correct |
8 | Correct | 3 ms | 620 KB | Output is correct |
9 | Correct | 3 ms | 640 KB | Output is correct |
10 | Correct | 3 ms | 620 KB | Output is correct |
11 | Correct | 3 ms | 620 KB | Output is correct |
12 | Correct | 2 ms | 492 KB | Output is correct |
13 | Correct | 187 ms | 27884 KB | Output is correct |
14 | Correct | 118 ms | 17900 KB | Output is correct |
15 | Correct | 133 ms | 19180 KB | Output is correct |
16 | Correct | 142 ms | 20844 KB | Output is correct |
17 | Correct | 165 ms | 24428 KB | Output is correct |
18 | Correct | 221 ms | 32492 KB | Output is correct |
19 | Correct | 146 ms | 21484 KB | Output is correct |
20 | Correct | 136 ms | 20588 KB | Output is correct |
21 | Correct | 174 ms | 25068 KB | Output is correct |
22 | Correct | 222 ms | 29696 KB | Output is correct |
23 | Correct | 187 ms | 28268 KB | Output is correct |
24 | Correct | 185 ms | 27628 KB | Output is correct |
25 | Correct | 192 ms | 27628 KB | Output is correct |
26 | Correct | 191 ms | 20588 KB | Output is correct |
27 | Correct | 180 ms | 26348 KB | Output is correct |
28 | Correct | 189 ms | 26112 KB | Output is correct |
29 | Correct | 276 ms | 33900 KB | Output is correct |
30 | Correct | 190 ms | 27756 KB | Output is correct |
31 | Correct | 164 ms | 24556 KB | Output is correct |
32 | Correct | 317 ms | 89452 KB | Output is correct |
33 | Correct | 140 ms | 44396 KB | Output is correct |
34 | Correct | 138 ms | 39148 KB | Output is correct |
35 | Correct | 195 ms | 50284 KB | Output is correct |
36 | Correct | 177 ms | 36972 KB | Output is correct |
37 | Correct | 185 ms | 29548 KB | Output is correct |
38 | Correct | 347 ms | 106604 KB | Output is correct |
39 | Correct | 4 ms | 1132 KB | Output is correct |
40 | Correct | 3 ms | 748 KB | Output is correct |
41 | Correct | 3 ms | 748 KB | Output is correct |
42 | Correct | 2 ms | 620 KB | Output is correct |
43 | Correct | 3 ms | 748 KB | Output is correct |
44 | Correct | 3 ms | 748 KB | Output is correct |
45 | Correct | 3 ms | 748 KB | Output is correct |
46 | Correct | 2 ms | 748 KB | Output is correct |
47 | Correct | 5 ms | 1260 KB | Output is correct |
48 | Correct | 4 ms | 1004 KB | Output is correct |
49 | Correct | 4 ms | 1144 KB | Output is correct |
50 | Correct | 4 ms | 1132 KB | Output is correct |
51 | Correct | 4 ms | 1132 KB | Output is correct |
52 | Correct | 3 ms | 1004 KB | Output is correct |
53 | Correct | 3 ms | 876 KB | Output is correct |
54 | Correct | 3 ms | 876 KB | Output is correct |
55 | Correct | 3 ms | 1004 KB | Output is correct |
56 | Correct | 3 ms | 748 KB | Output is correct |
57 | Correct | 233 ms | 46188 KB | Output is correct |
58 | Correct | 186 ms | 37996 KB | Output is correct |
59 | Correct | 255 ms | 52344 KB | Output is correct |
60 | Correct | 152 ms | 31596 KB | Output is correct |
61 | Correct | 164 ms | 33772 KB | Output is correct |
62 | Correct | 179 ms | 34668 KB | Output is correct |
63 | Correct | 270 ms | 56556 KB | Output is correct |
64 | Correct | 212 ms | 39532 KB | Output is correct |
65 | Correct | 271 ms | 56940 KB | Output is correct |
66 | Correct | 261 ms | 70764 KB | Output is correct |
67 | Correct | 335 ms | 90988 KB | Output is correct |
68 | Correct | 235 ms | 64816 KB | Output is correct |
69 | Correct | 271 ms | 80968 KB | Output is correct |
70 | Correct | 169 ms | 37996 KB | Output is correct |
71 | Correct | 298 ms | 72132 KB | Output is correct |
72 | Correct | 191 ms | 45676 KB | Output is correct |
73 | Correct | 227 ms | 49900 KB | Output is correct |
74 | Correct | 150 ms | 37100 KB | Output is correct |
75 | Correct | 241 ms | 61112 KB | Output is correct |
76 | Correct | 165 ms | 42708 KB | Output is correct |
77 | Correct | 258 ms | 79468 KB | Output is correct |
78 | Correct | 152 ms | 34060 KB | Output is correct |
79 | Correct | 214 ms | 52588 KB | Output is correct |
80 | Correct | 257 ms | 65708 KB | Output is correct |
81 | Correct | 158 ms | 31724 KB | Output is correct |
82 | Correct | 204 ms | 40172 KB | Output is correct |
83 | Correct | 138 ms | 24812 KB | Output is correct |
84 | Correct | 143 ms | 22764 KB | Output is correct |
85 | Correct | 138 ms | 27116 KB | Output is correct |
86 | Correct | 254 ms | 44268 KB | Output is correct |
87 | Correct | 137 ms | 27244 KB | Output is correct |
88 | Correct | 367 ms | 105384 KB | Output is correct |
89 | Correct | 190 ms | 35948 KB | Output is correct |
90 | Correct | 173 ms | 35180 KB | Output is correct |
91 | Correct | 435 ms | 118620 KB | Output is correct |
92 | Correct | 326 ms | 100332 KB | Output is correct |
93 | Correct | 408 ms | 111468 KB | Output is correct |
94 | Correct | 393 ms | 111724 KB | Output is correct |
95 | Correct | 382 ms | 98540 KB | Output is correct |
96 | Correct | 302 ms | 82796 KB | Output is correct |
97 | Correct | 358 ms | 105196 KB | Output is correct |
98 | Correct | 290 ms | 69612 KB | Output is correct |
99 | Correct | 288 ms | 79724 KB | Output is correct |
100 | Correct | 276 ms | 77032 KB | Output is correct |