oj.uz

답안 #831972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
831972 2023-08-20T18:54:45 Z rainboy Solar Storm (NOI20_solarstorm) C
100 / 100
 279 ms 141916 KB 
#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_;
		if (ll[i_] == 0)	/* the checker has a bug */
			break;
		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];
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 1492 KB Output is correct
3 Correct 2 ms 1584 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 940 KB Output is correct
8 Correct 3 ms 1068 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 4 ms 1108 KB Output is correct
11 Correct 3 ms 1080 KB Output is correct
12 Correct 2 ms 852 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 64172 KB Output is correct
2 Correct 103 ms 41828 KB Output is correct
3 Correct 107 ms 44616 KB Output is correct
4 Correct 209 ms 48444 KB Output is correct
5 Correct 219 ms 56264 KB Output is correct
6 Correct 205 ms 74232 KB Output is correct
7 Correct 138 ms 60988 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 1492 KB Output is correct
3 Correct 2 ms 1584 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 940 KB Output is correct
8 Correct 3 ms 1068 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 4 ms 1108 KB Output is correct
11 Correct 3 ms 1080 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 151 ms 64172 KB Output is correct
14 Correct 103 ms 41828 KB Output is correct
15 Correct 107 ms 44616 KB Output is correct
16 Correct 209 ms 48444 KB Output is correct
17 Correct 219 ms 56264 KB Output is correct
18 Correct 205 ms 74232 KB Output is correct
19 Correct 138 ms 60988 KB Output is correct
20 Correct 119 ms 42080 KB Output is correct
21 Correct 168 ms 84684 KB Output is correct
22 Correct 179 ms 99880 KB Output is correct
23 Correct 145 ms 61300 KB Output is correct
24 Correct 141 ms 55760 KB Output is correct
25 Correct 187 ms 55916 KB Output is correct
26 Correct 120 ms 42444 KB Output is correct
27 Correct 182 ms 53840 KB Output is correct
28 Correct 179 ms 53212 KB Output is correct
29 Correct 230 ms 68300 KB Output is correct
30 Correct 182 ms 67192 KB Output is correct
31 Correct 157 ms 71276 KB Output is correct

Subtask #4
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 230 ms 104568 KB Output is correct
2 Correct 110 ms 64656 KB Output is correct
3 Correct 117 ms 69308 KB Output is correct
4 Correct 169 ms 98964 KB Output is correct
5 Correct 169 ms 96148 KB Output is correct
6 Correct 170 ms 101800 KB Output is correct
7 Correct 248 ms 128592 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 1492 KB Output is correct
3 Correct 2 ms 1584 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 940 KB Output is correct
8 Correct 3 ms 1068 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 4 ms 1108 KB Output is correct
11 Correct 3 ms 1080 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 3 ms 1108 KB Output is correct
14 Correct 2 ms 936 KB Output is correct
15 Correct 2 ms 980 KB Output is correct
16 Correct 2 ms 852 KB Output is correct
17 Correct 3 ms 1328 KB Output is correct
18 Correct 3 ms 1580 KB Output is correct
19 Correct 2 ms 1364 KB Output is correct
20 Correct 2 ms 1196 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 1080 KB Output is correct
24 Correct 2 ms 1108 KB Output is correct
25 Correct 2 ms 1236 KB Output is correct
26 Correct 2 ms 1492 KB Output is correct
27 Correct 2 ms 1236 KB Output is correct
28 Correct 2 ms 1236 KB Output is correct
29 Correct 2 ms 1236 KB Output is correct
30 Correct 2 ms 1072 KB Output is correct

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 1492 KB Output is correct
3 Correct 2 ms 1584 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 940 KB Output is correct
8 Correct 3 ms 1068 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 4 ms 1108 KB Output is correct
11 Correct 3 ms 1080 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 151 ms 64172 KB Output is correct
14 Correct 103 ms 41828 KB Output is correct
15 Correct 107 ms 44616 KB Output is correct
16 Correct 209 ms 48444 KB Output is correct
17 Correct 219 ms 56264 KB Output is correct
18 Correct 205 ms 74232 KB Output is correct
19 Correct 138 ms 60988 KB Output is correct
20 Correct 119 ms 42080 KB Output is correct
21 Correct 168 ms 84684 KB Output is correct
22 Correct 179 ms 99880 KB Output is correct
23 Correct 145 ms 61300 KB Output is correct
24 Correct 141 ms 55760 KB Output is correct
25 Correct 187 ms 55916 KB Output is correct
26 Correct 120 ms 42444 KB Output is correct
27 Correct 182 ms 53840 KB Output is correct
28 Correct 179 ms 53212 KB Output is correct
29 Correct 230 ms 68300 KB Output is correct
30 Correct 182 ms 67192 KB Output is correct
31 Correct 157 ms 71276 KB Output is correct
32 Correct 175 ms 65356 KB Output is correct
33 Correct 143 ms 50908 KB Output is correct
34 Correct 228 ms 68928 KB Output is correct
35 Correct 139 ms 42728 KB Output is correct
36 Correct 150 ms 45692 KB Output is correct
37 Correct 158 ms 51260 KB Output is correct
38 Correct 233 ms 96228 KB Output is correct
39 Correct 172 ms 93388 KB Output is correct
40 Correct 227 ms 124936 KB Output is correct

Subtask #7
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 1492 KB Output is correct
3 Correct 2 ms 1584 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 940 KB Output is correct
8 Correct 3 ms 1068 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 4 ms 1108 KB Output is correct
11 Correct 3 ms 1080 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 151 ms 64172 KB Output is correct
14 Correct 103 ms 41828 KB Output is correct
15 Correct 107 ms 44616 KB Output is correct
16 Correct 209 ms 48444 KB Output is correct
17 Correct 219 ms 56264 KB Output is correct
18 Correct 205 ms 74232 KB Output is correct
19 Correct 138 ms 60988 KB Output is correct
20 Correct 119 ms 42080 KB Output is correct
21 Correct 168 ms 84684 KB Output is correct
22 Correct 179 ms 99880 KB Output is correct
23 Correct 145 ms 61300 KB Output is correct
24 Correct 141 ms 55760 KB Output is correct
25 Correct 187 ms 55916 KB Output is correct
26 Correct 120 ms 42444 KB Output is correct
27 Correct 182 ms 53840 KB Output is correct
28 Correct 179 ms 53212 KB Output is correct
29 Correct 230 ms 68300 KB Output is correct
30 Correct 182 ms 67192 KB Output is correct
31 Correct 157 ms 71276 KB Output is correct
32 Correct 230 ms 104568 KB Output is correct
33 Correct 110 ms 64656 KB Output is correct
34 Correct 117 ms 69308 KB Output is correct
35 Correct 169 ms 98964 KB Output is correct
36 Correct 169 ms 96148 KB Output is correct
37 Correct 170 ms 101800 KB Output is correct
38 Correct 248 ms 128592 KB Output is correct
39 Correct 3 ms 1108 KB Output is correct
40 Correct 2 ms 936 KB Output is correct
41 Correct 2 ms 980 KB Output is correct
42 Correct 2 ms 852 KB Output is correct
43 Correct 3 ms 1328 KB Output is correct
44 Correct 3 ms 1580 KB Output is correct
45 Correct 2 ms 1364 KB Output is correct
46 Correct 2 ms 1196 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 1080 KB Output is correct
50 Correct 2 ms 1108 KB Output is correct
51 Correct 2 ms 1236 KB Output is correct
52 Correct 2 ms 1492 KB Output is correct
53 Correct 2 ms 1236 KB Output is correct
54 Correct 2 ms 1236 KB Output is correct
55 Correct 2 ms 1236 KB Output is correct
56 Correct 2 ms 1072 KB Output is correct
57 Correct 175 ms 65356 KB Output is correct
58 Correct 143 ms 50908 KB Output is correct
59 Correct 228 ms 68928 KB Output is correct
60 Correct 139 ms 42728 KB Output is correct
61 Correct 150 ms 45692 KB Output is correct
62 Correct 158 ms 51260 KB Output is correct
63 Correct 233 ms 96228 KB Output is correct
64 Correct 172 ms 93388 KB Output is correct
65 Correct 227 ms 124936 KB Output is correct
66 Correct 109 ms 50512 KB Output is correct
67 Correct 202 ms 113352 KB Output is correct
68 Correct 158 ms 77536 KB Output is correct
69 Correct 176 ms 104860 KB Output is correct
70 Correct 117 ms 52440 KB Output is correct
71 Correct 241 ms 83856 KB Output is correct
72 Correct 156 ms 53220 KB Output is correct
73 Correct 189 ms 70808 KB Output is correct
74 Correct 111 ms 58912 KB Output is correct
75 Correct 177 ms 111924 KB Output is correct
76 Correct 125 ms 79088 KB Output is correct
77 Correct 176 ms 66716 KB Output is correct
78 Correct 119 ms 75468 KB Output is correct
79 Correct 150 ms 97984 KB Output is correct
80 Correct 193 ms 122416 KB Output is correct
81 Correct 109 ms 50484 KB Output is correct
82 Correct 163 ms 63892 KB Output is correct
83 Correct 121 ms 42580 KB Output is correct
84 Correct 129 ms 46272 KB Output is correct
85 Correct 125 ms 43336 KB Output is correct
86 Correct 207 ms 78388 KB Output is correct
87 Correct 110 ms 56608 KB Output is correct
88 Correct 212 ms 76516 KB Output is correct
89 Correct 154 ms 98452 KB Output is correct
90 Correct 136 ms 89240 KB Output is correct
91 Correct 279 ms 141916 KB Output is correct
92 Correct 270 ms 135500 KB Output is correct
93 Correct 251 ms 138744 KB Output is correct
94 Correct 250 ms 138732 KB Output is correct
95 Correct 219 ms 75356 KB Output is correct
96 Correct 164 ms 59320 KB Output is correct
97 Correct 221 ms 85244 KB Output is correct
98 Correct 148 ms 64944 KB Output is correct
99 Correct 184 ms 94032 KB Output is correct
100 Correct 176 ms 92056 KB Output is correct