# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
643576 |
2022-09-22T14:23:50 Z |
Cyber_Wolf |
Miners (IOI07_miners) |
C++14 |
|
280 ms |
524288 KB |
// Problem: P4 - Miners
// Contest: DMOJ - IOI '07
// URL: https://dmoj.ca/problem/ioi07p4
// Memory Limit: 16 MB
// Time Limit: 750 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define lg long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const lg N = 1e5+5;
lg dp[N][32][32];
lg n;
string s;
vector<lg> v(N);
lg solve(lg idx, lg g, lg h)
{
if(idx == n)
{
return 0;
}
auto &ret = dp[idx][g][h];
if(~ret) return ret;
lg x = g/4, y = (g&3), a = h/4, b = (h&3);
set<lg> se1;
if(v[idx] != 3) se1.insert(v[idx]);
if(x != 3) se1.insert(x);
if(y != 3) se1.insert(y);
set<lg> se2;
if(v[idx] != 3) se2.insert(v[idx]);
if(a != 3) se2.insert(a);
if(b != 3) se2.insert(b);
lg ch1 = solve(idx+1, v[idx]*4+x, a*4+b)+se1.size();
lg ch2 = solve(idx+1, x*4+y, v[idx]*4+a)+se2.size();
return ret = max(ch1, ch2);
}
int main()
{
fastio;
cin >> n >> s;
for(int i = 0; i < n; i++)
{
if(s[i] == 'M') v[i] = 1;
if(s[i] == 'B') v[i] = 2;
for(int j = 0; j < 32; j++)
{
for(int k = 0; k < 32; k++)
{
dp[i][j][k] = -1;
}
}
}
cout << solve(0, 3*4+3, 3*4+3) << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
42928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
143 ms |
85564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
280 ms |
211424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
225 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
199 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |