oj.uz

Submission #666470

# Submission time Handle Problem Language Result Execution time Memory
666470 2022-11-28T16:50:09 Z rainboy Bodyguard (JOI21_bodyguard) C
42 / 100
 25000 ms 285344 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 25019 ms 159148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 282816 KB Output is correct
2 Correct 314 ms 282624 KB Output is correct
3 Correct 288 ms 272756 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 307 ms 222044 KB Output is correct
6 Correct 254 ms 191988 KB Output is correct
7 Correct 280 ms 222308 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 282816 KB Output is correct
2 Correct 314 ms 282624 KB Output is correct
3 Correct 288 ms 272756 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 307 ms 222044 KB Output is correct
6 Correct 254 ms 191988 KB Output is correct
7 Correct 280 ms 222308 KB Output is correct
8 Correct 449 ms 283732 KB Output is correct
9 Correct 463 ms 281928 KB Output is correct
10 Correct 424 ms 270472 KB Output is correct
11 Correct 9 ms 804 KB Output is correct
12 Correct 472 ms 222188 KB Output is correct
13 Correct 450 ms 192160 KB Output is correct
14 Correct 437 ms 222292 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 282816 KB Output is correct
2 Correct 314 ms 282624 KB Output is correct
3 Correct 288 ms 272756 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 307 ms 222044 KB Output is correct
6 Correct 254 ms 191988 KB Output is correct
7 Correct 280 ms 222308 KB Output is correct
8 Correct 449 ms 283732 KB Output is correct
9 Correct 463 ms 281928 KB Output is correct
10 Correct 424 ms 270472 KB Output is correct
11 Correct 9 ms 804 KB Output is correct
12 Correct 472 ms 222188 KB Output is correct
13 Correct 450 ms 192160 KB Output is correct
14 Correct 437 ms 222292 KB Output is correct
15 Correct 2419 ms 285344 KB Output is correct
16 Correct 2227 ms 285276 KB Output is correct
17 Correct 1668 ms 273436 KB Output is correct
18 Correct 40 ms 1696 KB Output is correct
19 Correct 2721 ms 223248 KB Output is correct
20 Correct 2907 ms 193216 KB Output is correct
21 Correct 1958 ms 223124 KB Output is correct

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Execution timed out 25019 ms 159148 KB Time limit exceeded
2 Halted 0 ms 0 KB -