oj.uz

Submission #538692

# Submission time Handle Problem Language Result Execution time Memory
538692 2022-03-17T13:45:44 Z Mitsubachi JOI15_cardgame2 (JOI15_cardgame2) C++14
100 / 100
 1774 ms 509992 KB 
//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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1134 ms 509772 KB Output is correct
2 Correct 1086 ms 509864 KB Output is correct
3 Correct 1078 ms 509792 KB Output is correct
4 Correct 1194 ms 509684 KB Output is correct
5 Correct 1144 ms 509776 KB Output is correct
6 Correct 1101 ms 509776 KB Output is correct
7 Correct 1115 ms 509896 KB Output is correct
8 Correct 1108 ms 509860 KB Output is correct
9 Correct 1102 ms 509696 KB Output is correct
10 Correct 1082 ms 509732 KB Output is correct
11 Correct 1108 ms 509816 KB Output is correct
12 Correct 1106 ms 509696 KB Output is correct
13 Correct 1106 ms 509792 KB Output is correct
14 Correct 1104 ms 509676 KB Output is correct
15 Correct 1103 ms 509728 KB Output is correct
16 Correct 1108 ms 509728 KB Output is correct
17 Correct 1115 ms 509780 KB Output is correct
18 Correct 1094 ms 509800 KB Output is correct
19 Correct 1151 ms 509832 KB Output is correct
20 Correct 1134 ms 509856 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1134 ms 509772 KB Output is correct
2 Correct 1086 ms 509864 KB Output is correct
3 Correct 1078 ms 509792 KB Output is correct
4 Correct 1194 ms 509684 KB Output is correct
5 Correct 1144 ms 509776 KB Output is correct
6 Correct 1101 ms 509776 KB Output is correct
7 Correct 1115 ms 509896 KB Output is correct
8 Correct 1108 ms 509860 KB Output is correct
9 Correct 1102 ms 509696 KB Output is correct
10 Correct 1082 ms 509732 KB Output is correct
11 Correct 1108 ms 509816 KB Output is correct
12 Correct 1106 ms 509696 KB Output is correct
13 Correct 1106 ms 509792 KB Output is correct
14 Correct 1104 ms 509676 KB Output is correct
15 Correct 1103 ms 509728 KB Output is correct
16 Correct 1108 ms 509728 KB Output is correct
17 Correct 1115 ms 509780 KB Output is correct
18 Correct 1094 ms 509800 KB Output is correct
19 Correct 1151 ms 509832 KB Output is correct
20 Correct 1134 ms 509856 KB Output is correct
21 Correct 1112 ms 509796 KB Output is correct
22 Correct 1112 ms 509796 KB Output is correct
23 Correct 1150 ms 509904 KB Output is correct
24 Correct 1106 ms 509888 KB Output is correct
25 Correct 1125 ms 509724 KB Output is correct
26 Correct 1118 ms 509740 KB Output is correct
27 Correct 1117 ms 509776 KB Output is correct
28 Correct 1104 ms 509804 KB Output is correct
29 Correct 1154 ms 509692 KB Output is correct
30 Correct 1138 ms 509792 KB Output is correct
31 Correct 1154 ms 509880 KB Output is correct
32 Correct 1113 ms 509932 KB Output is correct
33 Correct 1087 ms 509828 KB Output is correct
34 Correct 1116 ms 509884 KB Output is correct
35 Correct 1119 ms 509912 KB Output is correct
36 Correct 1123 ms 509800 KB Output is correct
37 Correct 1098 ms 509768 KB Output is correct
38 Correct 1114 ms 509832 KB Output is correct
39 Correct 1127 ms 509720 KB Output is correct
40 Correct 1103 ms 509780 KB Output is correct

Subtask #3
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1134 ms 509772 KB Output is correct
2 Correct 1086 ms 509864 KB Output is correct
3 Correct 1078 ms 509792 KB Output is correct
4 Correct 1194 ms 509684 KB Output is correct
5 Correct 1144 ms 509776 KB Output is correct
6 Correct 1101 ms 509776 KB Output is correct
7 Correct 1115 ms 509896 KB Output is correct
8 Correct 1108 ms 509860 KB Output is correct
9 Correct 1102 ms 509696 KB Output is correct
10 Correct 1082 ms 509732 KB Output is correct
11 Correct 1108 ms 509816 KB Output is correct
12 Correct 1106 ms 509696 KB Output is correct
13 Correct 1106 ms 509792 KB Output is correct
14 Correct 1104 ms 509676 KB Output is correct
15 Correct 1103 ms 509728 KB Output is correct
16 Correct 1108 ms 509728 KB Output is correct
17 Correct 1115 ms 509780 KB Output is correct
18 Correct 1094 ms 509800 KB Output is correct
19 Correct 1151 ms 509832 KB Output is correct
20 Correct 1134 ms 509856 KB Output is correct
21 Correct 1112 ms 509796 KB Output is correct
22 Correct 1112 ms 509796 KB Output is correct
23 Correct 1150 ms 509904 KB Output is correct
24 Correct 1106 ms 509888 KB Output is correct
25 Correct 1125 ms 509724 KB Output is correct
26 Correct 1118 ms 509740 KB Output is correct
27 Correct 1117 ms 509776 KB Output is correct
28 Correct 1104 ms 509804 KB Output is correct
29 Correct 1154 ms 509692 KB Output is correct
30 Correct 1138 ms 509792 KB Output is correct
31 Correct 1154 ms 509880 KB Output is correct
32 Correct 1113 ms 509932 KB Output is correct
33 Correct 1087 ms 509828 KB Output is correct
34 Correct 1116 ms 509884 KB Output is correct
35 Correct 1119 ms 509912 KB Output is correct
36 Correct 1123 ms 509800 KB Output is correct
37 Correct 1098 ms 509768 KB Output is correct
38 Correct 1114 ms 509832 KB Output is correct
39 Correct 1127 ms 509720 KB Output is correct
40 Correct 1103 ms 509780 KB Output is correct
41 Correct 1114 ms 509780 KB Output is correct
42 Correct 1107 ms 509936 KB Output is correct
43 Correct 1137 ms 509792 KB Output is correct
44 Correct 1126 ms 509788 KB Output is correct
45 Correct 1140 ms 509736 KB Output is correct
46 Correct 1109 ms 509840 KB Output is correct
47 Correct 1108 ms 509924 KB Output is correct
48 Correct 1110 ms 509904 KB Output is correct
49 Correct 1078 ms 509916 KB Output is correct
50 Correct 1086 ms 509828 KB Output is correct
51 Correct 1083 ms 509716 KB Output is correct
52 Correct 1049 ms 509908 KB Output is correct
53 Correct 1058 ms 509932 KB Output is correct
54 Correct 1069 ms 509744 KB Output is correct
55 Correct 1078 ms 509928 KB Output is correct
56 Correct 1066 ms 509992 KB Output is correct
57 Correct 1057 ms 509852 KB Output is correct
58 Correct 1065 ms 509908 KB Output is correct
59 Correct 1055 ms 509824 KB Output is correct
60 Correct 1049 ms 509896 KB Output is correct
61 Correct 1061 ms 509764 KB Output is correct
62 Correct 1063 ms 509796 KB Output is correct
63 Correct 1774 ms 509940 KB Output is correct
64 Correct 1475 ms 509712 KB Output is correct
65 Correct 1318 ms 509820 KB Output is correct
66 Correct 1234 ms 509820 KB Output is correct
67 Correct 1244 ms 509820 KB Output is correct