제출 #899536

#제출 시각아이디문제언어결과실행 시간메모리
899536NonozeMiners (IOI07_miners)C++17
100 / 100
1286 ms458464 KiB
#include <bits/stdc++.h> #define sz(x) (int)(x.size()) using namespace std; int n; 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=seq[empl]; int s1=dp(empl+1, vaut, prec11, prec21, prec22); int s2=dp(empl+1, prec11, prec12, vaut, prec21); set<int> f1, f2; f1.insert(vaut), f2.insert(vaut); if (prec11!=0) f1.insert(prec11); if (prec12!=0) f1.insert(prec12); if (prec21!=0) f2.insert(prec21); if (prec22!=0) f2.insert(prec22); s1+=f1.size(); s2+=f2.size(); 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))))); for (auto &u: seq) { if (u=='M') u=1; else if (u=='F') u=2; else u=3; } 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...