제출 #378455

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378455		rainboy	Fireworks (APIO16_fireworks)	C11	55 / 100	112 ms	184300 KiB

fireworks

#include <stdio.h>
#include <string.h>

#define N	5000
#define INF	0x3f3f3f3f3f3f3f3fLL

long long min(long long a, long long b) { return a < b ? a : b; }

int merge(int *dd1, long long *ll1, int k1, int *dd2, long long *ll2, int k2) {
	static int dd[N];
	static long long ll[N];
	int k, h1, h2;

	k = 0, h1 = h2 = 0;
	while (h1 < k1 && h2 < k2) {
		long long l = min(ll1[h1], ll2[h2]);

		dd[k] = dd1[h1] + dd2[h2], ll[k] = l, k++;
		if ((ll1[h1] -= l) == 0)
			h1++;
		if ((ll2[h2] -= l) == 0)
			h2++;
	}
	memcpy(dd1, dd, k * sizeof *dd);
	memcpy(ll1, ll, k * sizeof *ll);
	return k;
}

int main() {
	static int pp[N], cc[N], dd[N][N], kk[N];
	static long long dp[N], ll[N][N];
	int n, m, n_, h, i;
	long long ans;

	scanf("%d%d", &n, &m), n_ = n + m;
	for (i = 1; i < n_; i++)
		scanf("%d%d", &pp[i], &cc[i]), pp[i]--;
	for (i = n_ - 1; i > 0; i--) {
		int p;

		dp[i] += cc[i];
		for (h = kk[i]; h > 0 && dd[i][h - 1] >= -1; h--)
			dd[i][h] = dd[i][h - 1], ll[i][h] = ll[i][h - 1];
		dd[i][h] = -1, ll[i][h] = cc[i], kk[i]++;
		while (kk[i] && dd[i][kk[i] - 1] >= 1)
			kk[i]--;
		dd[i][kk[i]] = 1, ll[i][kk[i]] = INF, kk[i]++;
		p = pp[i];
		dp[p] += dp[i];
		if (kk[p] == 0)
			memcpy(dd[p], dd[i], kk[i] * sizeof *dd[i]), memcpy(ll[p], ll[i], kk[i] * sizeof *ll[i]), kk[p] = kk[i];
		else
			kk[p] = merge(dd[p], ll[p], kk[p], dd[i], ll[i], kk[i]);
	}
	ans = dp[0];
	for (h = 0; h < kk[0] && dd[i][h] < 0; h++)
		ans += dd[i][h] * ll[i][h];
	printf("%lld\n", ans);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

fireworks.c: In function 'main':
fireworks.c:35:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   35 |  scanf("%d%d", &n, &m), n_ = n + m;
      |  ^~~~~~~~~~~~~~~~~~~~~
fireworks.c:37:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   37 |   scanf("%d%d", &pp[i], &cc[i]), pp[i]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 0 / 45