Submission #1191142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191142		JooDdae	매우 즐거운 카드 게임 (JOI15_cardgame2)	C++20	0 / 100	0 ms	324 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], 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]);
	cout << ans;
}

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