제출 #392221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
392221		rainboy	휴가 (IOI14_holiday)	C11	0 / 100	5048 ms	56736 KiB

holiday

#include "holiday.h"
#include <stdio.h>

#define N	100000
#define A	100000000
#define LG	30	/* LG = ceil(log2(A)) */
#define N_	(N * (LG + 1))

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

int ll[1 + N_], rr[1 + N_], kk[1 + N_], _; long long xx[1 + N_];

int update(int t, int l, int r, int i, int x) {
	int t_ = _++;

	kk[t_] = kk[t] + 1, xx[t_] = xx[t] + x;
	if (r - l > 1) {
		int m = (l + r) / 2;

		if (i < m)
			ll[t_] = update(ll[t], l, m, i, x), rr[t_] = rr[t];
		else
			ll[t_] = ll[t], rr[t_] = update(rr[t], m, r, i, x);
	}
	return t_;
}

long long query(int t, int k) {
	int l, r, m;
	long long sum;

	l = 0, r = A + 1, sum = 0;
	while (r - l > 1) {
		m = (l + r) / 2;
		if (k < kk[ll[t]])
			r = m, t = ll[t];
		else
			l = m, k -= kk[ll[t]], sum += xx[ll[t]], t = rr[t];
	}
	sum += (long long) min(kk[t], k) * (A - l);
	return sum;
}

int tt[N];

void solve_(long long *dp, int l, int r, int il, int ir, int c) {
	int m, i, im;
	long long d_;

	if (l == r)
		return;
	m = (l + r) / 2;
	im = -1, d_ = -1;
	for (i = il; i < ir; i++) {
		long long d = m - i * c < 0 ? -1 : query(tt[i], m - i * c);

		if (d_ < d)
			d_ = d, im = i;
	}
	dp[m] = d_;
	solve_(dp, l, m, il, ir, c), solve_(dp, m + 1, r, il, ir, c);
}

void solve(int *aa, long long *dp1, long long *dp2, int n) {
	int i, t;

	_ = 1;
	for (i = 0, t = 0; i < n; i++)
		tt[i] = t = update(t, 0, A + 1, A - aa[i], aa[i]);
	solve_(dp1, 0, n * 2, 0, n, 1);
	solve_(dp2, 0, n * 3, 0, n, 2);
}

long long findMaxAttraction(int n, int s, int d_, int aa[]) {
	static int aa_[N];
	static long long dp1[N * 2], dp2[N * 3], dq1[N * 2], dq2[N * 3];
	int i, d;
	long long ans;

	for (i = s; i >= 0; i--)
		aa_[s - i] = aa[i];
	solve(aa_, dp1, dp2, s + 1);
	for (i = s + 1; i < n; i++)
		aa_[i - s - 1] = aa[i];
	solve(aa_, dq1, dq2, n - 1 - s);
	for (d = d_; d >= 0; d--)
		dq1[d] = d == 0 ? 0 : dq1[d - 1], dq2[d] = d < 2 ? 0 : dq2[d - 2];
	ans = 0;
	for (d = 0; d <= d_; d++)
		ans = max(ans, max(dq2[d] + dp1[d_ - d], dp2[d] + dq1[d_ - d]));
	return ans;
}

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

holiday.c: In function 'solve_':
holiday.c:48:12: warning: variable 'im' set but not used [-Wunused-but-set-variable]
   48 |  int m, i, im;
      |            ^~
grader.c: In function 'main':
grader.c:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
    7 |     int i, n_s;
      |            ^~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53