# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
899509 |
2024-01-06T10:56:43 Z |
Nonoze |
Miners (IOI07_miners) |
C++17 |
|
1500 ms |
308504 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;
map<pair<int, pair<pair<int, int>, pair<int, int>>>, int> memo;
int dp(int empl, pair<int, int> prec1, pair<int, int> prec2) {
if (empl>=n) return 0;
if (memo.count({empl, {prec1, prec2}})) return memo[{empl, {prec1, prec2}}];
int vaut=1;
if (seq[empl]=='F') vaut=2;
if (seq[empl]=='B') vaut=4;
int s1=dp(empl+1, {prec1.second, vaut}, prec2);
int s2=dp(empl+1, prec1, {prec2.second, vaut});
int mask1=vaut;
mask1|=prec1.first;
mask1|=prec1.second;
int mask2=vaut;
mask2|=prec2.first;
mask2|=prec2.second;
s1+=__builtin_popcount(mask1);
s2+=__builtin_popcount(mask2);
return memo[{empl, {prec1, prec2}}]=max(s1, s2);
}
void solve() {
cin >> n;
cin >> seq;
memo.clear();
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 |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
500 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 |
16 ms |
3416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
8796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
191 ms |
36100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
521 ms |
80740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1125 ms |
196248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1611 ms |
308504 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |