#include <stdio.h>
#include <stdlib.h>
#define N 1000000
int max(int a, int b) { return a > b ? a : b; }
int n, k;
long long xx[N], ss[N + 1]; int ll[N], rr[N];
int *ej[N], eo[N];
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
int qu[N], cnt; long long s_; int i_;
void dfs(int i) {
int o;
long long s;
qu[cnt++] = i;
s = ss[rr[i]] - ss[ll[qu[max(cnt - k, 0)]]];
if (s_ < s)
s_ = s, i_ = i;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
dfs(j);
}
cnt--;
}
int main() {
static int pp[N];
int i, j, l, r;
long long d;
scanf("%d%d%lld", &n, &k, &d);
for (i = 1; i < n; i++)
scanf("%lld", &xx[i]), xx[i] += xx[i - 1];
for (i = 1; i <= n; i++)
scanf("%lld", &ss[i]), ss[i] += ss[i - 1];
for (i = 0, l = 0, r = 0; i < n; i++) {
while (l < i && xx[i] - xx[l] > d)
l++;
while (r < n && xx[r] - xx[i] <= d)
r++;
ll[i] = l, rr[i] = r;
}
for (i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (i = 0, j = 1; j < n; j++) {
while (rr[i] < ll[j])
i++;
pp[j] = i, append(i, j);
}
s_ = 0, i_ = -1, dfs(0);
cnt = 0;
while (cnt < k && i_ != -1)
qu[cnt++] = i_, i_ = pp[i_];
printf("%d\n", cnt);
while (cnt--)
printf("%d ", qu[cnt] + 1);
printf("\n");
return 0;
}
Compilation message
SolarStorm.c: In function 'append':
SolarStorm.c:15:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
15 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
SolarStorm.c: In function 'main':
SolarStorm.c:43:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
43 | scanf("%d%d%lld", &n, &k, &d);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SolarStorm.c:45:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | scanf("%lld", &xx[i]), xx[i] += xx[i - 1];
| ^~~~~~~~~~~~~~~~~~~~~
SolarStorm.c:47:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | scanf("%lld", &ss[i]), ss[i] += ss[i - 1];
| ^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
1448 KB |
Output is correct |
3 |
Correct |
2 ms |
1620 KB |
Output is correct |
4 |
Correct |
1 ms |
852 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
3 ms |
980 KB |
Output is correct |
7 |
Correct |
2 ms |
980 KB |
Output is correct |
8 |
Correct |
2 ms |
1108 KB |
Output is correct |
9 |
Correct |
2 ms |
852 KB |
Output is correct |
10 |
Correct |
2 ms |
1108 KB |
Output is correct |
11 |
Correct |
2 ms |
1076 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
144 ms |
68224 KB |
Output is correct |
2 |
Correct |
94 ms |
43484 KB |
Output is correct |
3 |
Correct |
99 ms |
46624 KB |
Output is correct |
4 |
Correct |
163 ms |
50784 KB |
Output is correct |
5 |
Correct |
213 ms |
59500 KB |
Output is correct |
6 |
Correct |
197 ms |
79416 KB |
Output is correct |
7 |
Correct |
123 ms |
63508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
1448 KB |
Output is correct |
3 |
Correct |
2 ms |
1620 KB |
Output is correct |
4 |
Correct |
1 ms |
852 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
3 ms |
980 KB |
Output is correct |
7 |
Correct |
2 ms |
980 KB |
Output is correct |
8 |
Correct |
2 ms |
1108 KB |
Output is correct |
9 |
Correct |
2 ms |
852 KB |
Output is correct |
10 |
Correct |
2 ms |
1108 KB |
Output is correct |
11 |
Correct |
2 ms |
1076 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
13 |
Correct |
144 ms |
68224 KB |
Output is correct |
14 |
Correct |
94 ms |
43484 KB |
Output is correct |
15 |
Correct |
99 ms |
46624 KB |
Output is correct |
16 |
Correct |
163 ms |
50784 KB |
Output is correct |
17 |
Correct |
213 ms |
59500 KB |
Output is correct |
18 |
Correct |
197 ms |
79416 KB |
Output is correct |
19 |
Correct |
123 ms |
63508 KB |
Output is correct |
20 |
Correct |
103 ms |
46036 KB |
Output is correct |
21 |
Correct |
134 ms |
90176 KB |
Output is correct |
22 |
Correct |
169 ms |
107052 KB |
Output is correct |
23 |
Correct |
135 ms |
66456 KB |
Output is correct |
24 |
Correct |
133 ms |
62240 KB |
Output is correct |
25 |
Correct |
155 ms |
62316 KB |
Output is correct |
26 |
Correct |
110 ms |
46512 KB |
Output is correct |
27 |
Correct |
157 ms |
59668 KB |
Output is correct |
28 |
Correct |
170 ms |
59120 KB |
Output is correct |
29 |
Correct |
231 ms |
76864 KB |
Output is correct |
30 |
Correct |
167 ms |
73708 KB |
Output is correct |
31 |
Correct |
141 ms |
76588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
251 ms |
108236 KB |
Output is correct |
2 |
Correct |
107 ms |
65996 KB |
Output is correct |
3 |
Correct |
109 ms |
70936 KB |
Output is correct |
4 |
Correct |
198 ms |
102632 KB |
Output is correct |
5 |
Correct |
155 ms |
99488 KB |
Output is correct |
6 |
Correct |
169 ms |
105404 KB |
Output is correct |
7 |
Correct |
252 ms |
133872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
1448 KB |
Output is correct |
3 |
Correct |
2 ms |
1620 KB |
Output is correct |
4 |
Correct |
1 ms |
852 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
3 ms |
980 KB |
Output is correct |
7 |
Correct |
2 ms |
980 KB |
Output is correct |
8 |
Correct |
2 ms |
1108 KB |
Output is correct |
9 |
Correct |
2 ms |
852 KB |
Output is correct |
10 |
Correct |
2 ms |
1108 KB |
Output is correct |
11 |
Correct |
2 ms |
1076 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
13 |
Correct |
3 ms |
1108 KB |
Output is correct |
14 |
Correct |
2 ms |
980 KB |
Output is correct |
15 |
Correct |
2 ms |
944 KB |
Output is correct |
16 |
Correct |
2 ms |
852 KB |
Output is correct |
17 |
Correct |
3 ms |
1408 KB |
Output is correct |
18 |
Correct |
2 ms |
1588 KB |
Output is correct |
19 |
Correct |
2 ms |
1328 KB |
Output is correct |
20 |
Correct |
2 ms |
1236 KB |
Output is correct |
21 |
Correct |
3 ms |
1620 KB |
Output is correct |
22 |
Correct |
2 ms |
1620 KB |
Output is correct |
23 |
Correct |
3 ms |
1108 KB |
Output is correct |
24 |
Incorrect |
3 ms |
1108 KB |
Damaged module blocking communication between protected modules |
25 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
1448 KB |
Output is correct |
3 |
Correct |
2 ms |
1620 KB |
Output is correct |
4 |
Correct |
1 ms |
852 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
3 ms |
980 KB |
Output is correct |
7 |
Correct |
2 ms |
980 KB |
Output is correct |
8 |
Correct |
2 ms |
1108 KB |
Output is correct |
9 |
Correct |
2 ms |
852 KB |
Output is correct |
10 |
Correct |
2 ms |
1108 KB |
Output is correct |
11 |
Correct |
2 ms |
1076 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
13 |
Correct |
144 ms |
68224 KB |
Output is correct |
14 |
Correct |
94 ms |
43484 KB |
Output is correct |
15 |
Correct |
99 ms |
46624 KB |
Output is correct |
16 |
Correct |
163 ms |
50784 KB |
Output is correct |
17 |
Correct |
213 ms |
59500 KB |
Output is correct |
18 |
Correct |
197 ms |
79416 KB |
Output is correct |
19 |
Correct |
123 ms |
63508 KB |
Output is correct |
20 |
Correct |
103 ms |
46036 KB |
Output is correct |
21 |
Correct |
134 ms |
90176 KB |
Output is correct |
22 |
Correct |
169 ms |
107052 KB |
Output is correct |
23 |
Correct |
135 ms |
66456 KB |
Output is correct |
24 |
Correct |
133 ms |
62240 KB |
Output is correct |
25 |
Correct |
155 ms |
62316 KB |
Output is correct |
26 |
Correct |
110 ms |
46512 KB |
Output is correct |
27 |
Correct |
157 ms |
59668 KB |
Output is correct |
28 |
Correct |
170 ms |
59120 KB |
Output is correct |
29 |
Correct |
231 ms |
76864 KB |
Output is correct |
30 |
Correct |
167 ms |
73708 KB |
Output is correct |
31 |
Correct |
141 ms |
76588 KB |
Output is correct |
32 |
Correct |
170 ms |
73384 KB |
Output is correct |
33 |
Correct |
151 ms |
56452 KB |
Output is correct |
34 |
Correct |
209 ms |
77624 KB |
Output is correct |
35 |
Correct |
136 ms |
46696 KB |
Output is correct |
36 |
Correct |
138 ms |
50180 KB |
Output is correct |
37 |
Correct |
149 ms |
56596 KB |
Output is correct |
38 |
Correct |
230 ms |
106120 KB |
Output is correct |
39 |
Correct |
162 ms |
99848 KB |
Output is correct |
40 |
Correct |
251 ms |
135064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
1448 KB |
Output is correct |
3 |
Correct |
2 ms |
1620 KB |
Output is correct |
4 |
Correct |
1 ms |
852 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
3 ms |
980 KB |
Output is correct |
7 |
Correct |
2 ms |
980 KB |
Output is correct |
8 |
Correct |
2 ms |
1108 KB |
Output is correct |
9 |
Correct |
2 ms |
852 KB |
Output is correct |
10 |
Correct |
2 ms |
1108 KB |
Output is correct |
11 |
Correct |
2 ms |
1076 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
13 |
Correct |
144 ms |
68224 KB |
Output is correct |
14 |
Correct |
94 ms |
43484 KB |
Output is correct |
15 |
Correct |
99 ms |
46624 KB |
Output is correct |
16 |
Correct |
163 ms |
50784 KB |
Output is correct |
17 |
Correct |
213 ms |
59500 KB |
Output is correct |
18 |
Correct |
197 ms |
79416 KB |
Output is correct |
19 |
Correct |
123 ms |
63508 KB |
Output is correct |
20 |
Correct |
103 ms |
46036 KB |
Output is correct |
21 |
Correct |
134 ms |
90176 KB |
Output is correct |
22 |
Correct |
169 ms |
107052 KB |
Output is correct |
23 |
Correct |
135 ms |
66456 KB |
Output is correct |
24 |
Correct |
133 ms |
62240 KB |
Output is correct |
25 |
Correct |
155 ms |
62316 KB |
Output is correct |
26 |
Correct |
110 ms |
46512 KB |
Output is correct |
27 |
Correct |
157 ms |
59668 KB |
Output is correct |
28 |
Correct |
170 ms |
59120 KB |
Output is correct |
29 |
Correct |
231 ms |
76864 KB |
Output is correct |
30 |
Correct |
167 ms |
73708 KB |
Output is correct |
31 |
Correct |
141 ms |
76588 KB |
Output is correct |
32 |
Correct |
251 ms |
108236 KB |
Output is correct |
33 |
Correct |
107 ms |
65996 KB |
Output is correct |
34 |
Correct |
109 ms |
70936 KB |
Output is correct |
35 |
Correct |
198 ms |
102632 KB |
Output is correct |
36 |
Correct |
155 ms |
99488 KB |
Output is correct |
37 |
Correct |
169 ms |
105404 KB |
Output is correct |
38 |
Correct |
252 ms |
133872 KB |
Output is correct |
39 |
Correct |
3 ms |
1108 KB |
Output is correct |
40 |
Correct |
2 ms |
980 KB |
Output is correct |
41 |
Correct |
2 ms |
944 KB |
Output is correct |
42 |
Correct |
2 ms |
852 KB |
Output is correct |
43 |
Correct |
3 ms |
1408 KB |
Output is correct |
44 |
Correct |
2 ms |
1588 KB |
Output is correct |
45 |
Correct |
2 ms |
1328 KB |
Output is correct |
46 |
Correct |
2 ms |
1236 KB |
Output is correct |
47 |
Correct |
3 ms |
1620 KB |
Output is correct |
48 |
Correct |
2 ms |
1620 KB |
Output is correct |
49 |
Correct |
3 ms |
1108 KB |
Output is correct |
50 |
Incorrect |
3 ms |
1108 KB |
Damaged module blocking communication between protected modules |
51 |
Halted |
0 ms |
0 KB |
- |