Submission #899521

#TimeUsernameProblemLanguageResultExecution timeMemory
899521NonozeMiners (IOI07_miners)C++17
92 / 100
852 ms524288 KiB
#include <bits/stdc++.h> #define int long long #define sz(x) (int)(x.size()) using namespace std; int n, k, m; string seq; vector<vector<vector<vector<vector<int>>>>> memo; int dp(int empl, int prec11, int prec12, int prec21, int prec22) { if (empl>=n) return 0; if (memo[empl][prec11][prec12][prec21][prec22]!=-1) { return memo[empl][prec11][prec12][prec21][prec22]; } int vaut=1; if (seq[empl]=='F') vaut=2; if (seq[empl]=='B') vaut=3; int s1=dp(empl+1, prec12, vaut, prec21, prec22); int s2=dp(empl+1, prec11, prec12, prec22, vaut); set<int> f1, f2; f1.insert(vaut), f2.insert(vaut); f1.insert(prec11), f1.insert(prec12); f2.insert(prec21), f2.insert(prec22); s1+=f1.size()-f1.count(0); s2+=f2.size()-f2.count(0); return memo[empl][prec11][prec12][prec21][prec22]=max(s1, s2); } void solve() { cin >> n; cin >> seq; memo.clear(); memo.resize(n, vector<vector<vector<vector<int>>>>(4, vector<vector<vector<int>>> (4, vector<vector<int>> (4, vector<int>(4, -1))))); cout << dp(0, 0, 0, 0, 0) << endl; return; } signed main() { ios::sync_with_stdio(0); cin.tie(0); int tt=1;// cin >> tt; while(tt--) 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...