제출 #159460

#제출 시각아이디문제언어결과실행 시간메모리
159460InfiniteJestMiners (IOI07_miners)C++14
100 / 100
249 ms108792 KiB
#include <iostream> #include <fstream> #include <vector> #include <queue> #include <algorithm> #include <math.h> #include <map> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; ifstream in("input.txt"); ofstream out("output.txt"); typedef long long ll; int n; int v[100001]; int dp[100001][4][4][4][4]; int funz(int a, int b, int c){ if(b==3&&c==3){ b=a; c=a; } else if(c==3&&b!=3){ c=a; } if(a!=b&&b!=c&&a!=c)return 3; if(a==b&&b!=c)return 2; if(a==b&&b==c)return 1; if(a==c&&c!=b)return 2; return 2; } int rec(int pos, int a1, int a2, int b1, int b2){ if(pos==n)return 0; if(dp[pos][a1][a2][b1][b2]!=-1)return dp[pos][a1][a2][b1][b2]; dp[pos][a1][a2][b1][b2]=max(funz(v[pos],a1,a2)+rec(pos+1,v[pos],a1,b1,b2),funz(v[pos],b1,b2)+rec(pos+1,a1,a2,v[pos],b1)); //cout<<"pos "<<pos<<" a1 "<<a1<<" a2 "<<a2<<" b1 "<<b1<<" b2 "<<b2<<" dp "<<dp[pos][a1][a2][b1][b2]<<endl; return dp[pos][a1][a2][b1][b2]; } int main(){ cin>>n; for(int i=0;i<n;i++){ char g; cin>>g; if(g=='B')v[i]=0; else if(g=='M')v[i]=1; else if(g=='F')v[i]=2; } for(int i=0;i<n;i++){ for(int y=0;y<4;y++){ for(int j=0;j<4;j++){ for(int u=0;u<4;u++){ for(int h=0;h<4;h++){ dp[i][y][j][u][h]=-1; } } } } } cout<<rec(0,3,3,3,3); }
#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...