# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
899515 |
2024-01-06T11:12:40 Z |
Nonoze |
Miners (IOI07_miners) |
C++17 |
|
833 ms |
524288 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define sz(x) (int)(x.size())
using namespace std;
using namespace __gnu_pbds;
typedef
tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int n, k, m;
string seq;
vector<vector<vector<vector<vector<int>>>>> memo;
int dp(int empl, pair<int, int> prec1, pair<int, int> prec2) {
if (empl>=n) return 0;
if (memo[empl][prec1.first][prec1.second][prec2.first][prec2.second]!=-1) {
return memo[empl][prec1.first][prec1.second][prec2.first][prec2.second];
}
int vaut=1;
if (seq[empl]=='F') vaut=2;
if (seq[empl]=='B') vaut=3;
int s1=dp(empl+1, {prec1.second, vaut}, prec2);
int s2=dp(empl+1, prec1, {prec2.second, vaut});
set<int> f1, f2;
f1.insert(vaut), f2.insert(vaut);
f1.insert(prec1.first), f1.insert(prec1.second);
f2.insert(prec2.first), f2.insert(prec2.second);
s1+=f1.size()-f1.count(0);
s2+=f2.size()-f2.count(0);
return memo[empl][prec1.first][prec1.second][prec2.first][prec2.second]=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 time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
456 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 |
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 |
1 ms |
456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
5900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
28248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
131 ms |
56144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
277 ms |
140032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
833 ms |
419440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
340 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |