oj.uz

답안 #931364

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
931364 2024-02-21T16:32:33 Z rainboy 매트 (KOI15_mat) C
100 / 100
 28 ms 35676 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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