This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// 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][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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |