제출 #1191143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191143		JooDdae	매우 즐거운 카드 게임 (JOI15_cardgame2)	C++20	100 / 100	232 ms	7900 KiB

cardgame2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int INF = 1e9;

int n, a[505], b[505], c[505], dp[505][505][4], tmp[505][505][4];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i] >> b[i] >> c[i];
	if(n <= 2) return cout << (c[1] + (a[1] == a[2] || b[1] == b[2] ? c[2] : 0)), 0;

	for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) for(int k=0;k<4;k++) dp[i][j][k] = -INF;
	dp[1][2][3] = 0;

	int ans = 0;

	for(int p=3;p<=n;p++) {
		for(int i=1;i<=p;i++) for(int j=i+1;j<=p;j++) for(int k=0;k<4;k++) tmp[i][j][k] = -INF;

		for(int i=1;i<p;i++) for(int j=i+1;j<p;j++) for(int k=1;k<4;k++) if(dp[i][j][k] >= 0) {
			if(k & 1) {
				int B = (a[i] == a[j] || b[i] == b[j] ? 1 : 0) | (a[i] == a[p+1] || b[i] == b[p+1] ? 2 : 0);
				ans = max(ans, tmp[j][p][B] = max(tmp[j][p][B], dp[i][j][k] + c[i]));
			}
			if(k & 2) {
				int B = (a[i] == a[p] || b[i] == b[p] ? 1 : 0) | (a[p+1] == a[p] || b[p+1] == b[p] ? 2 : 0);
				ans = max(ans, tmp[i][j][B] = max(tmp[i][j][B], dp[i][j][k] + c[p]));
			}
		}

		memcpy(dp, tmp, sizeof tmp);
	}

	for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) for(int k=1;k<4;k+=2) ans = max(ans, dp[i][j][k] + c[i] + (a[i] == a[j] || b[i] == b[j] ? c[j] : 0));
	cout << ans;
}

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