제출 #1178143

#제출 시각아이디문제언어결과실행 시간메모리
1178143AlgorithmWarriorMiners (IOI07_miners)C++20
100 / 100
167 ms100644 KiB
#include <bits/stdc++.h> using namespace std; int const INF=1000000000; int const MAX=100005; int dp[MAX][4][4][4][4]; int n; char sir[MAX]; int distincte[4][4][4]; void read(){ cin>>n; cin.get(); cin.getline(sir+1,MAX); int i; for(i=1;i<=n;++i){ if(sir[i]=='B') sir[i]=1; if(sir[i]=='F') sir[i]=2; if(sir[i]=='M') sir[i]=3; } } int distinct(int a,int b,int c){ set<int>s; if(a) s.insert(a); if(b) s.insert(b); if(c) s.insert(c); return s.size(); } void get_distincte(){ int tip1,tip2,tip3; for(tip1=0;tip1<4;++tip1) for(tip2=0;tip2<4;++tip2) for(tip3=0;tip3<4;++tip3) distincte[tip1][tip2][tip3]=distinct(tip1,tip2,tip3); } void maxself(int& x,int val){ if(x<val) x=val; } int get_dp(){ int i,tip,tip1,tip2,tip3,tip4; for(tip1=0;tip1<4;++tip1) for(tip2=0;tip2<4;++tip2) for(tip3=0;tip3<4;++tip3) for(tip4=0;tip4<4;++tip4) dp[0][tip1][tip2][tip3][tip4]=-INF; dp[0][0][0][0][0]=0; for(i=1;i<=n;++i) for(tip1=0;tip1<4;++tip1) for(tip2=0;tip2<4;++tip2) for(tip3=0;tip3<4;++tip3) for(tip4=0;tip4<4;++tip4){ dp[i][tip1][tip2][tip3][tip4]=-INF; for(tip=0;tip<4;++tip){ if(tip1==sir[i]) maxself(dp[i][tip1][tip2][tip3][tip4],dp[i-1][tip2][tip][tip3][tip4]+distincte[tip1][tip2][tip]); if(tip3==sir[i]) maxself(dp[i][tip1][tip2][tip3][tip4],dp[i-1][tip1][tip2][tip4][tip]+distincte[tip3][tip4][tip]); } } int ans=-INF; for(tip1=0;tip1<4;++tip1) for(tip2=0;tip2<4;++tip2) for(tip3=0;tip3<4;++tip3) for(tip4=0;tip4<4;++tip4) maxself(ans,dp[n][tip1][tip2][tip3][tip4]); return ans; } int main() { read(); get_distincte(); cout<<get_dp(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...