Submission #378454

#	Time	Username	Problem	Language	Result	Execution time	Memory
378454		rainboy	Fireworks (APIO16_fireworks)	C11	0 / 100	1 ms	1016 KiB

fireworks

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

#define N	5000
#define INF	0x3f3f3f3f

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

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

	k = 0, h1 = h2 = 0;
	while (h1 < k1 || h2 < k2) {
		int l = min(h1 < k1 ? ll1[h1] : INF, h2 < k2 ? ll2[h2] : INF);

		dd[k] = (h1 < k1 ? dd1[h1] : 1) + (h2 < k2 ? dd2[h2] : 1), ll[k] = l, k++;
		if (h1 < k1 && (ll1[h1] -= l) == 0)
			h1++;
		if (h2 < k2 && (ll2[h2] -= l) == 0)
			h2++;
	}
	while (k > 0 && dd[k - 1] >= 1)
		k--;
	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], ll[N][N], kk[N];
	static long long dp[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]++;
		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]; h++)
		ans += (long long) dd[i][h] * ll[i][h];
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

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

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