#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]);
pp[0] = -1;
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];
| ^~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
1452 KB |
Output is correct |
3 |
Correct |
4 ms |
1580 KB |
Output is correct |
4 |
Correct |
2 ms |
852 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
932 KB |
Output is correct |
7 |
Correct |
2 ms |
940 KB |
Output is correct |
8 |
Correct |
3 ms |
1108 KB |
Output is correct |
9 |
Correct |
3 ms |
808 KB |
Output is correct |
10 |
Correct |
2 ms |
1120 KB |
Output is correct |
11 |
Correct |
3 ms |
1108 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
145 ms |
62860 KB |
Output is correct |
2 |
Correct |
145 ms |
40652 KB |
Output is correct |
3 |
Correct |
107 ms |
43428 KB |
Output is correct |
4 |
Correct |
200 ms |
47172 KB |
Output is correct |
5 |
Correct |
226 ms |
55028 KB |
Output is correct |
6 |
Correct |
250 ms |
72984 KB |
Output is correct |
7 |
Correct |
140 ms |
59700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
1452 KB |
Output is correct |
3 |
Correct |
4 ms |
1580 KB |
Output is correct |
4 |
Correct |
2 ms |
852 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
932 KB |
Output is correct |
7 |
Correct |
2 ms |
940 KB |
Output is correct |
8 |
Correct |
3 ms |
1108 KB |
Output is correct |
9 |
Correct |
3 ms |
808 KB |
Output is correct |
10 |
Correct |
2 ms |
1120 KB |
Output is correct |
11 |
Correct |
3 ms |
1108 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
13 |
Correct |
145 ms |
62860 KB |
Output is correct |
14 |
Correct |
145 ms |
40652 KB |
Output is correct |
15 |
Correct |
107 ms |
43428 KB |
Output is correct |
16 |
Correct |
200 ms |
47172 KB |
Output is correct |
17 |
Correct |
226 ms |
55028 KB |
Output is correct |
18 |
Correct |
250 ms |
72984 KB |
Output is correct |
19 |
Correct |
140 ms |
59700 KB |
Output is correct |
20 |
Correct |
130 ms |
40780 KB |
Output is correct |
21 |
Correct |
162 ms |
83460 KB |
Output is correct |
22 |
Correct |
194 ms |
98688 KB |
Output is correct |
23 |
Correct |
166 ms |
60004 KB |
Output is correct |
24 |
Correct |
149 ms |
54600 KB |
Output is correct |
25 |
Correct |
188 ms |
54764 KB |
Output is correct |
26 |
Correct |
121 ms |
41156 KB |
Output is correct |
27 |
Correct |
179 ms |
52456 KB |
Output is correct |
28 |
Correct |
169 ms |
51960 KB |
Output is correct |
29 |
Correct |
252 ms |
66980 KB |
Output is correct |
30 |
Correct |
167 ms |
65808 KB |
Output is correct |
31 |
Correct |
147 ms |
69924 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
235 ms |
103092 KB |
Output is correct |
2 |
Correct |
100 ms |
63264 KB |
Output is correct |
3 |
Correct |
141 ms |
68104 KB |
Output is correct |
4 |
Correct |
166 ms |
97656 KB |
Output is correct |
5 |
Correct |
168 ms |
94808 KB |
Output is correct |
6 |
Correct |
172 ms |
100324 KB |
Output is correct |
7 |
Correct |
263 ms |
127268 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
1452 KB |
Output is correct |
3 |
Correct |
4 ms |
1580 KB |
Output is correct |
4 |
Correct |
2 ms |
852 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
932 KB |
Output is correct |
7 |
Correct |
2 ms |
940 KB |
Output is correct |
8 |
Correct |
3 ms |
1108 KB |
Output is correct |
9 |
Correct |
3 ms |
808 KB |
Output is correct |
10 |
Correct |
2 ms |
1120 KB |
Output is correct |
11 |
Correct |
3 ms |
1108 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
13 |
Correct |
2 ms |
1108 KB |
Output is correct |
14 |
Correct |
2 ms |
948 KB |
Output is correct |
15 |
Correct |
2 ms |
980 KB |
Output is correct |
16 |
Correct |
2 ms |
852 KB |
Output is correct |
17 |
Correct |
2 ms |
1328 KB |
Output is correct |
18 |
Correct |
2 ms |
1600 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 |
3 ms |
1620 KB |
Output is correct |
23 |
Correct |
2 ms |
1072 KB |
Output is correct |
24 |
Incorrect |
2 ms |
1108 KB |
Damaged module blocking communication between protected modules |
25 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
1452 KB |
Output is correct |
3 |
Correct |
4 ms |
1580 KB |
Output is correct |
4 |
Correct |
2 ms |
852 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
932 KB |
Output is correct |
7 |
Correct |
2 ms |
940 KB |
Output is correct |
8 |
Correct |
3 ms |
1108 KB |
Output is correct |
9 |
Correct |
3 ms |
808 KB |
Output is correct |
10 |
Correct |
2 ms |
1120 KB |
Output is correct |
11 |
Correct |
3 ms |
1108 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
13 |
Correct |
145 ms |
62860 KB |
Output is correct |
14 |
Correct |
145 ms |
40652 KB |
Output is correct |
15 |
Correct |
107 ms |
43428 KB |
Output is correct |
16 |
Correct |
200 ms |
47172 KB |
Output is correct |
17 |
Correct |
226 ms |
55028 KB |
Output is correct |
18 |
Correct |
250 ms |
72984 KB |
Output is correct |
19 |
Correct |
140 ms |
59700 KB |
Output is correct |
20 |
Correct |
130 ms |
40780 KB |
Output is correct |
21 |
Correct |
162 ms |
83460 KB |
Output is correct |
22 |
Correct |
194 ms |
98688 KB |
Output is correct |
23 |
Correct |
166 ms |
60004 KB |
Output is correct |
24 |
Correct |
149 ms |
54600 KB |
Output is correct |
25 |
Correct |
188 ms |
54764 KB |
Output is correct |
26 |
Correct |
121 ms |
41156 KB |
Output is correct |
27 |
Correct |
179 ms |
52456 KB |
Output is correct |
28 |
Correct |
169 ms |
51960 KB |
Output is correct |
29 |
Correct |
252 ms |
66980 KB |
Output is correct |
30 |
Correct |
167 ms |
65808 KB |
Output is correct |
31 |
Correct |
147 ms |
69924 KB |
Output is correct |
32 |
Correct |
170 ms |
63960 KB |
Output is correct |
33 |
Correct |
173 ms |
49404 KB |
Output is correct |
34 |
Correct |
224 ms |
67612 KB |
Output is correct |
35 |
Correct |
136 ms |
41284 KB |
Output is correct |
36 |
Correct |
147 ms |
44332 KB |
Output is correct |
37 |
Correct |
154 ms |
49868 KB |
Output is correct |
38 |
Correct |
219 ms |
95076 KB |
Output is correct |
39 |
Correct |
181 ms |
91960 KB |
Output is correct |
40 |
Correct |
227 ms |
123928 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
1452 KB |
Output is correct |
3 |
Correct |
4 ms |
1580 KB |
Output is correct |
4 |
Correct |
2 ms |
852 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
932 KB |
Output is correct |
7 |
Correct |
2 ms |
940 KB |
Output is correct |
8 |
Correct |
3 ms |
1108 KB |
Output is correct |
9 |
Correct |
3 ms |
808 KB |
Output is correct |
10 |
Correct |
2 ms |
1120 KB |
Output is correct |
11 |
Correct |
3 ms |
1108 KB |
Output is correct |
12 |
Correct |
1 ms |
852 KB |
Output is correct |
13 |
Correct |
145 ms |
62860 KB |
Output is correct |
14 |
Correct |
145 ms |
40652 KB |
Output is correct |
15 |
Correct |
107 ms |
43428 KB |
Output is correct |
16 |
Correct |
200 ms |
47172 KB |
Output is correct |
17 |
Correct |
226 ms |
55028 KB |
Output is correct |
18 |
Correct |
250 ms |
72984 KB |
Output is correct |
19 |
Correct |
140 ms |
59700 KB |
Output is correct |
20 |
Correct |
130 ms |
40780 KB |
Output is correct |
21 |
Correct |
162 ms |
83460 KB |
Output is correct |
22 |
Correct |
194 ms |
98688 KB |
Output is correct |
23 |
Correct |
166 ms |
60004 KB |
Output is correct |
24 |
Correct |
149 ms |
54600 KB |
Output is correct |
25 |
Correct |
188 ms |
54764 KB |
Output is correct |
26 |
Correct |
121 ms |
41156 KB |
Output is correct |
27 |
Correct |
179 ms |
52456 KB |
Output is correct |
28 |
Correct |
169 ms |
51960 KB |
Output is correct |
29 |
Correct |
252 ms |
66980 KB |
Output is correct |
30 |
Correct |
167 ms |
65808 KB |
Output is correct |
31 |
Correct |
147 ms |
69924 KB |
Output is correct |
32 |
Correct |
235 ms |
103092 KB |
Output is correct |
33 |
Correct |
100 ms |
63264 KB |
Output is correct |
34 |
Correct |
141 ms |
68104 KB |
Output is correct |
35 |
Correct |
166 ms |
97656 KB |
Output is correct |
36 |
Correct |
168 ms |
94808 KB |
Output is correct |
37 |
Correct |
172 ms |
100324 KB |
Output is correct |
38 |
Correct |
263 ms |
127268 KB |
Output is correct |
39 |
Correct |
2 ms |
1108 KB |
Output is correct |
40 |
Correct |
2 ms |
948 KB |
Output is correct |
41 |
Correct |
2 ms |
980 KB |
Output is correct |
42 |
Correct |
2 ms |
852 KB |
Output is correct |
43 |
Correct |
2 ms |
1328 KB |
Output is correct |
44 |
Correct |
2 ms |
1600 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 |
3 ms |
1620 KB |
Output is correct |
49 |
Correct |
2 ms |
1072 KB |
Output is correct |
50 |
Incorrect |
2 ms |
1108 KB |
Damaged module blocking communication between protected modules |
51 |
Halted |
0 ms |
0 KB |
- |