Submission #788152

#	Time	Username	Problem	Language	Result	Execution time	Memory
788152		rainboy	Fruits (NOI22_fruits)	C11	35 / 100	1079 ms	17868 KiB

Main

#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 (stderr)

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 / 6
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 13 / 13
• Subtask 5: 0 / 23
• Subtask 6: 0 / 42