oj.uz

Submission #788152

# Submission time Handle Problem Language Result Execution time Memory
788152 2023-07-19T20:27:52 Z rainboy Fruits (NOI22_fruits) C
35 / 100
 1000 ms 17868 KB 
#include <stdio.h>

#define N	400000

long long max(long long a, long long b) { return a > b ? a : b; }

int main() {
	static int aa[N], cc[N];
	static long long ss[N + 1];
	static char used[N];
	static int kk[N + 1], xx[N], yy[N], dd[N];
	static long long dp[N];
	int n, k, i, j, l, a, x, y, d;
	long long z;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]), aa[i]--;
		if (aa[i] >= 0)
			used[aa[i]] = 1;
	}
	for (a = 0; a < n; a++)
		scanf("%d", &cc[a]);
	k = 0;
	for (a = 0; a < n; a++) {
		kk[a] = k;
		if (!used[a])
			ss[k + 1] = ss[k] + cc[a], k++;
	}
	kk[n] = k;
	if (k == n) {
		for (i = 0; i < n; i++)
			printf("%lld ", ss[n] - ss[n - 1 - i]);
		printf("\n");
		return 0;
	}
	l = 0, a = -1;
	for (j = 0; j < n; j++) {
		if (aa[j] == -2)
			l++;
		else if (a > aa[j])
			aa[j] = -1;
		else {
			a = aa[j];
			xx[j] = kk[aa[j]], yy[j] = l, dd[j] = xx[j] - yy[j];
			if (dd[j] < 0)
				aa[j] = -1;
		}
		if (aa[j] >= 0) {
			dp[j] = 0;
			for (i = j - 1; i >= 0; i--) {
				if (aa[i] < 0)
					continue;
				if (dd[i] >= dd[j])
					break;
				dp[j] = max(dp[j], dp[i] + ss[xx[j]] - ss[yy[i] + dd[j]]);
			}
			if (i >= 0)
				dp[j] = max(dp[j], dp[i] + ss[xx[j]] - ss[xx[i]]);
			else
				dp[j] = max(dp[j], ss[xx[j]] - ss[dd[j]]);
			dp[j] += cc[aa[j]];
		}
		x = kk[n], y = l, d = kk[n] - y;
		z = 0;
		for (i = j; i >= 0; i--) {
			if (aa[i] < 0)
				continue;
			if (dd[i] >= d)
				break;
			z = max(z, dp[i] + ss[x] - ss[yy[i] + d]);
		}
		if (i >= 0)
			z = max(z, dp[i] + ss[x] - ss[xx[i]]);
		else
			z = max(z, ss[x] - ss[d]);
		printf("%lld ", z);
	}
	printf("\n");
	return 0;
}

Compilation message

Main.c: In function 'main':
Main.c:16:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Main.c:18:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   scanf("%d", &aa[i]), aa[i]--;
      |   ^~~~~~~~~~~~~~~~~~~
Main.c:23:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   scanf("%d", &cc[a]);
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 5 ms 1108 KB Output is correct
4 Correct 47 ms 9168 KB Output is correct
5 Correct 111 ms 17868 KB Output is correct
6 Correct 0 ms 212 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 288 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 288 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 288 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 288 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 3 ms 340 KB Output is correct
30 Correct 2 ms 344 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 2 ms 340 KB Output is correct
34 Correct 2 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 0 ms 292 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 3 ms 340 KB Output is correct
39 Correct 2 ms 340 KB Output is correct
40 Correct 3 ms 436 KB Output is correct
41 Correct 3 ms 448 KB Output is correct
42 Correct 4 ms 340 KB Output is correct
43 Correct 3 ms 468 KB Output is correct
44 Correct 3 ms 340 KB Output is correct
45 Correct 4 ms 468 KB Output is correct
46 Correct 3 ms 468 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 1 ms 340 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 11028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 5 ms 1108 KB Output is correct
14 Correct 47 ms 9168 KB Output is correct
15 Correct 111 ms 17868 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 288 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 0 ms 340 KB Output is correct
33 Correct 0 ms 288 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 3 ms 340 KB Output is correct
36 Correct 2 ms 344 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 2 ms 340 KB Output is correct
40 Correct 2 ms 340 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 0 ms 292 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 3 ms 340 KB Output is correct
45 Correct 2 ms 340 KB Output is correct
46 Correct 3 ms 436 KB Output is correct
47 Correct 3 ms 448 KB Output is correct
48 Correct 4 ms 340 KB Output is correct
49 Correct 3 ms 468 KB Output is correct
50 Correct 3 ms 340 KB Output is correct
51 Correct 4 ms 468 KB Output is correct
52 Correct 3 ms 468 KB Output is correct
53 Correct 1 ms 340 KB Output is correct
54 Correct 1 ms 340 KB Output is correct
55 Execution timed out 1079 ms 11028 KB Time limit exceeded
56 Halted 0 ms 0 KB -