Submission #650118

#TimeUsernameProblemLanguageResultExecution timeMemory
650118esomerMiners (IOI07_miners)C++17
92 / 100
1569 ms608 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define endl "\n" const int MOD = 998244353; void solve(){ int n; cin >> n; string s; cin >> s; map<pair<pair<int, int>, pair<int, int>>, int> dp; dp[{{0, 0}, {0,0}}] = 0; for(int i = 0; i < n; i++){ map<pair<pair<int, int>, pair<int, int>>, int> nw; for(auto t : dp){ auto p = t.first; int c; if(s[i] == 'M') c = 1; else if(s[i] == 'F') c = 2; else c = 3; set<int> add; add.insert(c); add.insert(p.first.first); add.insert(p.first.second); add.erase(0); nw[{{p.first.second, c}, p.second}] = max(nw[{{p.first.second, c}, p.second}], t.second + (int)add.size()); add.clear(); add.insert(c); add.insert(p.second.first); add.insert(p.second.second); add.erase(0); nw[{p.first, {p.second.second, c}}] = max(nw[{p.first, {p.second.second, c}}], t.second + (int)add.size()); } dp = nw; } int ans = 0; for(auto p : dp) ans = max(ans, p.second); cout << ans << endl; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); //freopen("inpt.txt", "r", stdin); //freopen("out.txt", "w", stdout); //int tt; cin >> tt; int tt = 1; for(int t = 1; t <= tt; t++){ //cout << "Case #"<<t << ": "; 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...