Submission #554593

#	Time	Username	Problem	Language	Result	Execution time	Memory
554593		rainboy	매우 즐거운 카드 게임 (JOI15_cardgame2)	C11	100 / 100	258 ms	4276 KiB

cardgame2

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

#define N	500

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

int main() {
	static int xx[N], yy[N], vv[N], dp[N + 1][N + 1], dq[N + 1][N + 1], dp_[N + 1][N + 1], dq_[N + 1][N + 1];
	int n, i, j, k, ans;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d%d", &xx[i], &yy[i], &vv[i]);
	ans = 0;
	for (k = 2; k <= n + 1; k++) {
		for (i = 0; i < k; i++) {
			memset(dp_[i], -1, k * sizeof *dp_[i]);
			memset(dq_[i], -1, k * sizeof *dq_[i]);
		}
		if (k == 2) {
			dp_[1][0] = vv[0];
			if (n >= 3)
				dq_[0][1] = vv[2];
		} else
			for (i = 0; i + 1 < k; i++)
				for (j = 0; j + 1 < k; j++) {
					int x;

					if ((x = dp[i][j]) != -1) {
						if (xx[j] == xx[i] || yy[j] == yy[i])
							dp_[k - 1][i] = max(dp_[k - 1][i], x + vv[i]);
						if (k < n && (xx[j] == xx[k] || yy[j] == yy[k]))
							dq_[i][k - 1] = max(dq_[i][k - 1], x + vv[k]);
					}
					if ((x = dq[i][j]) != -1) {
						if (xx[k - 1] == xx[i] || yy[k - 1] == yy[i])
							dp_[j][i] = max(dp_[j][i], x + vv[i]);
						if (k < n && (xx[k - 1] == xx[k] || yy[k - 1] == yy[k]))
							dq_[i][j] = max(dq_[i][j], x + vv[k]);
					}
				}
		for (i = 0; i < k; i++)
			for (j = 0; j < k; j++) {
				dp[i][j] = dp_[i][j], dq[i][j] = dq_[i][j];
				ans = max(ans, max(dp[i][j], dq[i][j]));
			}
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

cardgame2.c: In function 'main':
cardgame2.c:12:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
cardgame2.c:14:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   scanf("%d%d%d", &xx[i], &yy[i], &vv[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 75 / 75