# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
899536 |
2024-01-06T11:51:08 Z |
Nonoze |
Miners (IOI07_miners) |
C++17 |
|
1286 ms |
458464 KB |
#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 time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
23132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
106 ms |
46268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
256 ms |
114876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
792 ms |
344044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1286 ms |
458464 KB |
Output is correct |