Submission #666470

#	Time	Username	Problem	Language	Result	Execution time	Memory
666470		rainboy	Bodyguard (JOI21_bodyguard)	C11	42 / 100	25019 ms	285344 KiB

bodyguard

#include <stdio.h>

#define M	2800
#define N	(M * 3 / 2)

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

unsigned int X = 12345;

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

long long *zz;

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)
			if (zz[ii[j]] == zz[i_])
				j++;
			else if (zz[ii[j]] < zz[i_]) {
				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;
	}
}

int compress(long long *xx, long long *xx_, int n) {
	static int ii[M * 2];
	int n_, i;

	for (i = 0; i < n; i++)
		ii[i] = i;
	zz = xx, sort(ii, 0, n);
	n_ = 0;
	for (i = 0; i < n; i++)
		if (i + 1 < n && xx[ii[i + 1]] == xx[ii[i]])
			xx[ii[i]] = n_;
		else
			xx_[n_] = xx[ii[i]], xx[ii[i]] = n_++;
	return n_;
}

int main() {
	static long long xx[M * 2], xx_[M * 2], yy[M * 2], yy_[M * 2], dp[N * N], aa[N * N], bb[N * N];
	static int cc[M];
	int nx, ny, m, q, h, i, i_, j, j_;

	scanf("%d%d", &m, &q);
	for (h = 0; h < m; h++) {
		long long t, a, b;

		scanf("%lld%lld%lld%d", &t, &a, &b, &cc[h]), cc[h] /= 2;
		if (a < b) {
			xx[h << 1 | 0] = t - a, yy[h << 1 | 0] = t + a;
			xx[h << 1 | 1] = t - a, yy[h << 1 | 1] = t + b * 2 - a;
		} else {
			xx[h << 1 | 0] = t - a, yy[h << 1 | 0] = t + a;
			xx[h << 1 | 1] = t + a - b * 2, yy[h << 1 | 1] = t + a;
		}
	}
	nx = compress(xx, xx_, m * 2);
	ny = compress(yy, yy_, m * 2);
	for (h = 0; h < m; h++)
		if (xx[h << 1 | 0] == xx[h << 1 | 1]) {
			i = xx[h << 1 | 0];
			for (j = yy[h << 1 | 0]; j < yy[h << 1 | 1]; j++)
				aa[i * ny + j] = max(aa[i * ny + j], cc[h]);
		} else {
			j = yy[h << 1 | 0];
			for (i = xx[h << 1 | 0]; i < xx[h << 1 | 1]; i++)
				bb[i * ny + j] = max(bb[i * ny + j], cc[h]);
		}
	for (i = nx - 1; i >= 0; i--)
		for (j = ny - 1; j >= 0; j--) {
			dp[i * ny + j] = 0;
			if (j + 1 < ny)
				dp[i * ny + j] = max(dp[i * ny + j], dp[i * ny + (j + 1)] + (yy_[j + 1] - yy_[j]) * aa[i * ny + j]);
			if (i + 1 < nx)
				dp[i * ny + j] = max(dp[i * ny + j], dp[(i + 1) * ny + j] + (xx_[i + 1] - xx_[i]) * bb[i * ny + j]);
		}
	while (q--) {
		int u, v, x, y;
		long long ans;

		scanf("%d%d", &u, &v), x = u - v, y = u + v;
		if (x > xx_[nx - 1] || y > yy_[ny - 1]) {
			printf("0\n");
			continue;
		}
		i = 0;
		while (xx_[i] < x)
			i++;
		j = 0;
		while (yy_[j] < y)
			j++;
		ans = 0;
		for (i_ = i; i_ < nx; i_++)
			ans = max(ans, dp[i_ * ny + j] + (yy_[j] - y) * (j == 0 ? 0 : aa[i_ * ny + (j - 1)]));
		for (j_ = j; j_ < ny; j_++)
			ans = max(ans, dp[i * ny + j_] + (xx_[i] - x) * (i == 0 ? 0 : bb[(i - 1) * ny + j_]));
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message (stderr)

bodyguard.c: In function 'main':
bodyguard.c:56:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf("%d%d", &m, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
bodyguard.c:60:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   scanf("%lld%lld%lld%d", &t, &a, &b, &cc[h]), cc[h] /= 2;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bodyguard.c:93:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   scanf("%d%d", &u, &v), x = u - v, y = u + v;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 0 / 52