Submission #197547

#TimeUsernameProblemLanguageResultExecution timeMemory
197547SamAndMiners (IOI07_miners)C++17
100 / 100
159 ms632 KiB
#include <bits/stdc++.h> using namespace std; #define m_p make_pair const int N=100005; const int INF=1000000000; int n; char a[N]; int dp[4][4][4][4]; int ydp[4][4][4][4]; int main() { //freopen("input.txt","r",stdin); cin>>n; cin>>a; for(int x1=0;x1<4;++x1) for(int y1=0;y1<4;++y1) for(int x2=0;x2<4;++x2) for(int y2=0;y2<4;++y2) dp[x1][y1][x2][y2]=-INF; dp[3][3][3][3]=0; for(int i=1;i<=n;++i) { for(int x1=0;x1<4;++x1) for(int y1=0;y1<4;++y1) for(int x2=0;x2<4;++x2) for(int y2=0;y2<4;++y2) ydp[x1][y1][x2][y2]=-INF; int z; if(a[i-1]=='M') z=0; else if(a[i-1]=='B') z=1; else z=2; for(int x1=0;x1<4;++x1) { for(int y1=0;y1<4;++y1) { for(int x2=0;x2<4;++x2) { for(int y2=0;y2<4;++y2) { int b[4]={}; b[x1]=1; b[y1]=1; b[z]=1; ydp[y1][z][x2][y2]=max(ydp[y1][z][x2][y2],dp[x1][y1][x2][y2]+b[0]+b[1]+b[2]); b[0]=0; b[1]=0; b[2]=0; b[x2]=1; b[y2]=1; b[z]=1; ydp[x1][y1][y2][z]=max(ydp[x1][y1][y2][z],dp[x1][y1][x2][y2]+b[0]+b[1]+b[2]); } } } } for(int x1=0;x1<4;++x1) for(int y1=0;y1<4;++y1) for(int x2=0;x2<4;++x2) for(int y2=0;y2<4;++y2) dp[x1][y1][x2][y2]=ydp[x1][y1][x2][y2]; } int ans=-INF; for(int x1=0;x1<4;++x1) for(int y1=0;y1<4;++y1) for(int x2=0;x2<4;++x2) for(int y2=0;y2<4;++y2) ans=max(ans,dp[x1][y1][x2][y2]); cout<<ans<<endl; 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...