Submission #1191144

#TimeUsernameProblemLanguageResultExecution timeMemory
1191144JooDdae매우 즐거운 카드 게임 (JOI15_cardgame2)C++20
100 / 100
240 ms7888 KiB
#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]; #define okay(x, y) (a[x] == a[y] || b[x] == b[y]) 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] + (okay(1, 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 = (okay(i, j) ? 1 : 0) | (okay(i, 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 = (okay(i, p) ? 1 : 0) | (okay(p+1, 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] + (okay(i, j) ? c[j] : 0)); cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...