제출 #672510

#제출 시각아이디문제언어결과실행 시간메모리
672510sudheerays123Miners (IOI07_miners)C++17
42 / 100
584 ms99736 KiB
#include<bits/stdc++.h> using namespace std; #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define ll long long int const ll N = 1e5+5 , INF = 1e18 , MOD = 1e9+7; ll dp[N][3][3][3][3]; vector<ll> a(N); ll n; ll chartoll(char x){ if(x == 'M') return 0ll; if(x == 'B') return 1ll; return 2ll; } ll go(ll i , ll pre1 , ll pre2 , ll pree1 , ll pree2){ if(i == n+1) return 0; if(dp[i][pre1][pre2][pree1][pree2] != -1) return dp[i][pre1][pre2][pree1][pree2]; set<ll> s1; if(pre1 != -1) s1.insert(pre1); if(pree1 != -1) s1.insert(pree1); s1.insert(a[i]); ll uuu = s1.size(); ll ans = uuu+go(i+1,a[i],pre2,pre1,pree2); set<ll> s2; if(pre2 != -1) s2.insert(pre2); if(pree2 != -1) s2.insert(pree2); s2.insert(a[i]); ll uu = s2.size(); ans = max(ans,uu+go(i+1,pre1,a[i],pree1,pre2)); return dp[i][pre1][pre2][pree1][pree2] = ans; } void solve(){ string s; cin >> n >> s; s = ' '+s; for(ll i = 1; i <= n; i++) a[i] = chartoll(s[i]); // if(n <= 20){ // ll ans = -INF; // for(ll i = 0; i < (1ll<<n); i++){ // vector<char> mine1,mine2; // for(ll j = 0; j < n; j++){ // if(i&(1ll<<j)) mine1.push_back(s[j+1]); // else mine2.push_back(s[j+1]); // } // ll score = 0; // for(ll j = 0; j < mine1.size(); j++){ // set<char> food; // for(ll k = j; k >= max(0ll,j-2); k--) food.insert(mine1[k]); // score += food.size(); // } // for(ll j = 0; j < mine2.size(); j++){ // set<char> food; // food.insert(mine2[j]); // for(ll k = j; k >= max(0ll,j-2); k--) food.insert(mine2[k]); // score += food.size(); // } // ans = max(ans,score); // } // cout << ans; // // return; // } memset(dp,-1,sizeof dp); cout << go(1,-1,-1,-1,-1); } int main(){ fast; ll tc = 1; // cin >> tc; while(tc--) solve(); 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...