Submission #538692

#	Time	Username	Problem	Language	Result	Execution time	Memory
538692		Mitsubachi	매우 즐거운 카드 게임 (JOI15_cardgame2)	C++14	100 / 100	1774 ms	509992 KiB

cardgame2

//g++ 6.cpp -std=c++14 -O2 -I .
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vst = vector<string>;
using vvst = vector<vst>;

#define fi first
#define se second
#define pb push_back
#define pq_big(T) priority_queue<T,vector<T>,less<T>>
#define pq_small(T) priority_queue<T,vector<T>,greater<T>>
#define all(a) a.begin(),a.end()
#define rep(i,start,end) for(ll i=start;i<(ll)(end);i++)
#define per(i,start,end) for(ll i=start;i>=(ll)(end);i--)
#define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end())

vector<vector<vvi>> dp(4,vector<vvi>(505,vector<vi>(505)));

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  rep(i,0,505){
    rep(j,i+1,505){
      rep(k,j+1,505){
        rep(l,0,4){
          //dp[l][i][j][k]=-1e9;
          dp[l][i][j].emplace_back(-1e9);
        }
      }
    }
  }

  /*
  DPを考える

  dp[i][j][k][l]として
  [1枚目のindex][2枚目のindex][3枚目のindex][どのカードが取れるか] の状態になっている時点での最大値

  で状態が500^3*8通り　3sec/1250MBならこれで妥当そう
  正確には状態数がi<j<kなのでもう少し削減できると思われ
  */
  
  
  int n;
  cin>>n;

  vvi v(n,vi(3));
  rep(i,0,n){
    rep(j,0,3){
      cin>>v[i][j];
    }
  }

  dp[3][0][1][0]=0;
  int ans=0;

  rep(i,0,505){
    rep(j,i+1,505){
      rep(k,j+1,505){
        rep(l,0,4){
          if(dp[l][i][j][k-j-1]<0)continue;
          //cout<<l<<" "<<i<<" "<<j<<" "<<k<<" : "<<dp[l][i][j][k-j-1]<<endl;
          ans=max(ans,dp[l][i][j][k-j-1]);

          rep(bit,0,2){
            if(l&(1<<bit)){
              // bit枚目のを取る
              if(bit==0){
                if(i>=n)continue;
                int x=v[i][2];

                int ni=j,nj=k,nk=k+1,bt=0;

                if(ni<n){
                  if(v[ni][0]==v[i][0]||v[ni][1]==v[i][1]){
                    bt+=1;
                  }
                }

                if(nk<n){
                  if(v[nk][0]==v[i][0]||v[nk][1]==v[i][1]){
                    bt+=2;
                  }
                }

                dp[bt][ni][nj][nk-nj-1]=max(dp[bt][ni][nj][nk-nj-1],dp[l][i][j][k-j-1]+x);
              }
              if(bit==1){
                if(k>=n)continue;
                int x=v[k][2];

                int ni=i,nj=j,nk=k+1,bt=0;

                if(ni<n){
                  if(v[ni][0]==v[k][0]||v[ni][1]==v[k][1]){
                    bt+=1;
                  }
                }

                if(nk<n){
                  if(v[nk][0]==v[k][0]||v[nk][1]==v[k][1]){
                    bt+=2;
                  }
                }

                dp[bt][ni][nj][nk-nj-1]=max(dp[bt][ni][nj][nk-nj-1],dp[l][i][j][k-j-1]+x);
              }
            }
          }
        }
      }
    }
  }
  
  cout<<ans<<endl;
  
}

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