Submission #931364

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
931364	2024-02-21T16:32:33 Z	rainboy	매트 (KOI15_mat)	C	100 / 100	28 ms	35676 KB

mat

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

#define N	3000

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

unsigned int Z = 12345;

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

int tt[N], xx[N * 2], yy[N], ww[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 = xx[ii[j]] != xx[i_] ? xx[ii[j]] - xx[i_] : (i_ & 1) - (ii[j] & 1);

			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;
	}
}

int main() {
	static int ii[N * 2], tt_[N], jj[N], yy_[N], ww_[N], dp[N + 1], dq[N][N + 1];
	int n, y_, i, i_, j, x;

	scanf("%d%d", &n, &y_);
	for (i = 0; i < n; i++)
		scanf("%d%d%d%d%d", &tt[i], &xx[i << 1 | 0], &xx[i << 1 | 1], &yy[i], &ww[i]);
	for (i = 0; i < n * 2; i++)
		ii[i] = i;
	sort(ii, 0, n * 2);
	for (i = 0, x = 0; i < n * 2; i++)
		if ((ii[i] & 1) == 0)
			ii[xx[ii[i]] = x++] = ii[i] >> 1;
		else
			xx[ii[i]] = x;
	memset(dp, -1, (n + 1) * sizeof *dp);
	for (i = 0; i < n; i++)
		memset(dq[i], -1, (n + 1) * sizeof *dq[i]);
	for (i = 0; i < n; i++) {
		i_ = ii[i];
		tt_[i] = tt[i_], jj[i] = xx[i_ << 1 | 1], yy_[i] = yy[i_], ww_[i] = ww[i_];
	}
	dp[0] = 0;
	for (i = 0; i < n; i++) {
		dp[i + 1] = max(dp[i + 1], dp[i]);
		dq[i][i] = max(dq[i][i], dp[i] + ww_[i]);
		for (j = i; j < jj[i]; j++) {
			x = dq[i][j];
			dq[i][j + 1] = max(dq[i][j + 1], x);
			if (tt_[i] != tt_[j] && yy_[i] + yy_[j] <= y_) {
				if (jj[j] <= jj[i])
					dq[i][jj[j]] = max(dq[i][jj[j]], x + ww_[j]);
				else
					dq[j][jj[i]] = max(dq[j][jj[i]], x + ww_[j]);
			}
		}
		dp[jj[i]] = max(dp[jj[i]], dq[i][jj[i]]);
	}
	printf("%d\n", dp[n]);
	return 0;
}

Compilation message

mat.c: In function 'main':
mat.c:42:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  scanf("%d%d", &n, &y_);
      |  ^~~~~~~~~~~~~~~~~~~~~~
mat.c:44:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   scanf("%d%d%d%d%d", &tt[i], &xx[i << 1 | 0], &xx[i << 1 | 1], &yy[i], &ww[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	428 KB	Output is correct
4	Correct	0 ms	600 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct

Subtask #2

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	592 KB	Output is correct
2	Correct	0 ms	424 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2908 KB	Output is correct
2	Correct	1 ms	2908 KB	Output is correct
3	Correct	1 ms	2908 KB	Output is correct
4	Correct	1 ms	2908 KB	Output is correct
5	Correct	1 ms	2908 KB	Output is correct

Subtask #4

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	35676 KB	Output is correct
2	Correct	15 ms	35676 KB	Output is correct
3	Correct	14 ms	35676 KB	Output is correct
4	Correct	16 ms	35676 KB	Output is correct
5	Correct	15 ms	35676 KB	Output is correct

Subtask #5

43.0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	35676 KB	Output is correct
2	Correct	28 ms	35676 KB	Output is correct
3	Correct	28 ms	35672 KB	Output is correct
4	Correct	27 ms	35672 KB	Output is correct
5	Correct	23 ms	35676 KB	Output is correct
6	Correct	7 ms	35676 KB	Output is correct
7	Correct	26 ms	35660 KB	Output is correct
8	Correct	26 ms	35672 KB	Output is correct
9	Correct	19 ms	35676 KB	Output is correct
10	Correct	27 ms	35676 KB	Output is correct