# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
643593 |
2022-09-22T14:50:01 Z |
Cyber_Wolf |
Miners (IOI07_miners) |
C++14 |
|
1052 ms |
142332 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 int
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const lg N = 1e5+5;
lg dp[N][256];
lg n;
string s;
vector<lg> v(N);
lg solve(lg idx, lg bit)
{
if(idx == n)
{
return 0;
}
auto &ret = dp[idx][bit];
if(~ret) return ret;
lg x = ((bit/64)&3), y = ((bit/16)&3), a = ((bit/4)&3), b = (bit&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]*64+x*16+a*4+b)+se1.size();
lg ch2 = solve(idx+1, x*64+y*16+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 < 256; j++)
{
dp[i][j] = -1;
}
}
cout << solve(0, 3*64+3*16+3*4+3) << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
2004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
7408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
126 ms |
14880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
222 ms |
35296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
389 ms |
101368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1052 ms |
142332 KB |
Output is correct |