제출 #434146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434146		rainboy	Salesman (IOI09_salesman)	C11	100 / 100	542 ms	36552 KiB

salesman

#include <stdio.h>

#define N	500000
#define X	500001
#define INF	0x3f3f3f3f3f3f3f3f

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

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

int tt[N], xx[N], yy[N];

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = tt[ii[j]] != tt[i_] ? tt[ii[j]] - tt[i_] : xx[ii[j]] - xx[i_];

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

void update(long long *ft, int i, long long x) {
	while (i <= X) {
		ft[i] = max(ft[i], x);
		i |= i + 1;
	}
}

long long query(long long *ft, int i) {
	long long x = -INF;

	while (i >= 0) {
		x = max(x, ft[i]);
		i &= i + 1, i--;
	}
	return x;
}

int main() {
	static long long ft1[X + 1], ft2[X + 1];
	static int ii[N];
	static long long dp[N], dq[N], dr[N];
	int n, u, d, s, h, i, j;

	scanf("%d%d%d%d", &n, &u, &d, &s);
	for (i = 0; i < n; i++) {
		scanf("%d%d%d", &tt[i], &xx[i], &yy[i]);
		ii[i] = i;
	}
	sort(ii, 0, n);
	for (i = 0; i <= X; i++)
		ft1[i] = ft2[i] = -INF;
	update(ft1, s, s * d), update(ft2, X - s, -s * u);
	for (i = 0; i < n; i = j) {
		int t = tt[ii[i]], x;

		j = i + 1;
		while (j < n && tt[ii[j]] == t)
			j++;
		for (h = i; h < j; h++) {
			x = xx[ii[h]];
			dr[h] = max(query(ft1, x) - x * d, query(ft2, X - x) + x * u);
		}
		for (h = i; h < j; h++) {
			dp[h] = dr[h];
			if (h > i)
				dp[h] = max(dp[h], dp[h - 1] - (xx[ii[h]] - xx[ii[h - 1]]) * d);
			dp[h] += yy[ii[h]];
		}
		for (h = j - 1; h >= i; h--) {
			dq[h] = dr[h];
			if (h + 1 < j)
				dq[h] = max(dq[h], dq[h + 1] - (xx[ii[h + 1]] - xx[ii[h]]) * u);
			dq[h] += yy[ii[h]];
		}
		for (h = i; h < j; h++)
			dr[h] = max(dp[h], dq[h]);
		for (h = i + 1; h < j; h++)
			dr[h] = max(dr[h], dr[h - 1] - (xx[ii[h]] - xx[ii[h - 1]]) * d);
		for (h = j - 2; h >= i; h--)
			dr[h] = max(dr[h], dr[h + 1] - (xx[ii[h + 1]] - xx[ii[h]]) * u);
		for (h = i; h < j; h++) {
			x = xx[ii[h]];
			update(ft1, x, dr[h] + x * d), update(ft2, X - x, dr[h] - x * u);
		}
	}
	printf("%lld\n", max(query(ft1, s) - s * d, query(ft2, X - s) + s * u));
	return 0;
}

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

salesman.c: In function 'main':
salesman.c:62:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%d%d%d%d", &n, &u, &d, &s);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.c:64:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   scanf("%d%d%d", &tt[i], &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100