제출 #843647

#제출 시각아이디문제언어결과실행 시간메모리
843647ZeroCoolMiners (IOI07_miners)C++14
100 / 100
652 ms254800 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define mp make_pair #define mt make_tuple #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() using ll = long long; using ld = long double; void solve(int T); void pre(); const int N = 1e5 + 5; const int M = 405; const int SQRT = 500; const int LOG = 20; const int INF = 1e18; const int MOD = 1e9+7; const ld EPS = 1e-9; void pre(){ #ifdef ONLINE_JUDGE ios::sync_with_stdio(false); cin.tie(0); #endif } int32_t main(){ pre(); int tt = 1; //cin>>tt; for(int i = 1;i<=tt;i++){ cerr<<"Case "<<i<<": "<<endl; solve(i); } return 0; } int n; string s; int dp[N][4][4][4][4]; bool vis[N][4][4][4][4]; int f(int i,int a,int b,int c,int d){ if(i == n)return 0; if(vis[i][a][b][c][d])return dp[i][a][b][c][d]; vis[i][a][b][c][d] = true; int x = 0; if(s[i] == 'M')x = 1; else if(s[i] =='F')x = 2; else x = 3; set<int> s; s.insert(a); s.insert(b); s.insert(x); int unq1 = s.size(); if(a == 0 || b == 0)unq1--; s.clear(); s.insert(c); s.insert(d); s.insert(x); int unq2 = s.size(); if(c == 0 || d == 0)unq2--; int ans = max(f(i+1,b,x,c,d) + unq1, f(i+1,a,b,d,x) + unq2); dp[i][a][b][c][d] = ans; return ans; } void solve(int T){ cin>>n>>s; cout<<f(0,0,0,0,0)<<endl; }
#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...