Submission #1202995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202995		vnedu	매우 즐거운 카드 게임 (JOI15_cardgame2)	C++17	100 / 100	175 ms	64684 KiB

cardgame2

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

const int N = 500 + 5;
bool dp[N][N][N];
int n,c[N],a[N],v[N];
long long p[N];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;++i) cin>>c[i]>>a[i]>>v[i];
    for(int i=1;i<=n+3;++i) p[i]=p[i-1]+v[i];
    dp[3][1][2]=1;
    long long ans=0;
    for(int k=3;k<=n+3;++k){
        for(int i=1;i<=n+3;++i){
            for(int j=1;j<=n+3;++j) if(dp[k][i][j]){
                if(i<j)
                {
                    ans=max(ans,p[k-1]-v[i]-v[j]);
                    if(k==3 || k-1>n || c[i]==c[k-1] || a[i]==a[k-1]) dp[k+1][j][i]=1;
                    if(k==3 || k-1>n || c[k-1]==c[k] || a[k-1]==a[k]) dp[k+1][i][j]=1;
                }
                else
                {
                    int ni=i,nj=k-1,nk=k,lst=j;
                    ans=max(ans,p[nk-1]-v[ni]-v[nj]);
                    if(lst>n || c[ni]==c[lst] || a[ni]==a[lst]) dp[nk+1][nj][ni]=1;
                    if(lst>n || c[nk]==c[lst] || a[nk]==a[lst]) dp[nk+1][ni][nj]=1;
                }
            }
        }
    }
    cout<<ans;
}
int main(void)
{
//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int testcase=1;
//    cin>>testcase;
    while(testcase--)
        solve();
    return 0;
}

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