Submission #1178141

#TimeUsernameProblemLanguageResultExecution timeMemory
1178141AlgorithmWarriorMiners (IOI07_miners)C++20
92 / 100
1596 ms92516 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]; 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 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]+distinct(tip1,tip2,tip)); if(tip3==sir[i]) maxself(dp[i][tip1][tip2][tip3][tip4],dp[i-1][tip1][tip2][tip4][tip]+distinct(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(); 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...