제출 #655331

#제출 시각아이디문제언어결과실행 시간메모리
655331NakeebMiners (IOI07_miners)C++17
84 / 100
1603 ms235284 KiB
#include<bits/stdc++.h> using namespace std; int n; string s; map<string,int>mp; int dp[100005][500]; int curr=1; int func(string a,string b) { if(mp[a+b]) return mp[a+b]; else return mp[a+b]=curr++; } int solve(int i, string a, string b) { if(i==n) return 0; if(~dp[i][func(a,b)]) return dp[i][func(a,b)]; string c=""; c+=a[0],c+=a[1],c+=s[i]; string d=""; d+=b[0],d+=b[1],d+=s[i]; int m=0,f=0,q=0; for(int i=0;i<3;i++) { if(c[i]=='M') m++; else if(c[i]=='F') f++; else if(c[i]=='B') q++; } string cc={c[1],c[2]}; int c1=solve(i+1,cc,b)+min(m,1)+min(f,1)+min(q,1); m=0,f=0,q=0; for(int i=0;i<3;i++) { if(d[i]=='M') m++; else if(d[i]=='F') f++; else if(d[i]=='B') q++; } string dd={d[1],d[2]}; int c2=solve(i+1,a,dd)+min(m,1)+min(f,1)+min(q,1); return dp[i][func(a,b)]=max(c1,c2); } int main() { memset(dp,-1 ,sizeof(dp)); cin>>n; cin>>s; cout<<solve(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...