Submission #344384

#TimeUsernameProblemLanguageResultExecution timeMemory
344384prasanth30Miners (IOI07_miners)C++14
92 / 100
1604 ms201064 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int const int INF=1e18; //dp[i][a][b][c][d] ith position, a,b first mine c,d second mine int to_int(char c){ if(c=='M')return 1; if(c=='F')return 2; return 3; } inline void solve(){ int n;cin>>n; string s;cin>>s; s=' '+s; int dp[n+1][4][4][4][4]={0}; int ans=0; int freq[4]; freq[1]=freq[2]=freq[3]=0; freq[0]=INF; freq[to_int(s[1])]++; for(int i=1;i<=n;i++){ //freq[to_int(s[i])]++; for(int a=0;a<4;a++){ for(int b=0;b<4;b++){ for(int c=0;c<4;c++){ //dp[i][s[i][a][b][c] for(int d=0;d<4;d++){ dp[i][a][b][c][d]=-INF; //cout<<"dp["<<i<<"]["<<a<<"]["<<b<<"]["<<c<<"]["<<d<<"]->"<<dp[i][a][b][c][d]<<"\n"; //ans=max(ans,dp[n][a][b][c][d]); } } } } } dp[1][to_int(s[1])][0][0][0]=1; dp[1][0][0][to_int(s[1])][0]=1; for(int i=2;i<=n;i++){ freq[to_int(s[i])]++; for(int a=0;a<4;a++){ for(int b=0;b<4;b++){ for(int c=0;c<4;c++){ //dp[i][s[i][a][b][c] for(int d=0;d<4;d++){ if(a==0&&d!=0)continue; if(b==0&&c!=0)continue; // 1 1 2 2 // --freq[a]; --freq[b]; --freq[c]; --freq[d]; if(freq[a]<0||freq[b]<0||freq[c]<0||freq[d]<0){ ++freq[a]; ++freq[b]; ++freq[c]; ++freq[d]; continue; } ++freq[a]; ++freq[b]; ++freq[c]; ++freq[d]; set<int> ss; for(int x:{to_int(s[i]),a,d}){ if(x!=0)ss.insert(x); } dp[i][to_int(s[i])][a][b][c]= max(dp[i-1][a][d][b][c]+(int)ss.size(), dp[i][to_int(s[i])][a][b][c]); dp[i][b][c][to_int(s[i])][a]= max(dp[i-1][b][c][a][d]+(int)ss.size(),dp[i][b][c][to_int(s[i])][a]); //ans=max(ans,dp[i][b][c][to_int(s[i])][a]); //ans=max(ans,dp[i][to_int(s[i])][a][b][c]); } } } } } //for(int i=1;i<=n;i++){ //freq[to_int(s[i])]++; for(int a=0;a<4;a++){ for(int b=0;b<4;b++){ for(int c=0;c<4;c++){ //dp[i][s[i][a][b][c] for(int d=0;d<4;d++){ //cout<<"dp["<<i<<"]["<<a<<"]["<<b<<"]["<<c<<"]["<<d<<"]->"<<dp[i][a][b][c][d]<<"\n"; ans=max(ans,dp[n][a][b][c][d]); } } } } //} cout<<ans; } signed main() { cin.tie(NULL)->sync_with_stdio(false); cout.tie(NULL); solve(); }
#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...