이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
using namespace std;
const int N = 1e5 + 5;
int dp[N][4][4][4][4],ans;
int get(char x){
if (x == 'M') return 1;
if (x == 'B') return 2;
return 3;
}
int getans(int a,int b,int c){
int mn = min({a,b,c}),mx = max({a,b,c});
int s = a+b+c;
a = mn,c = mx,b = s - a - c;
if (b == 0) return 1;
if (a == 0) {
if (b == c) return 1;
else return 2;
}
if (c == a) return 1;
if (b == a || b == c) return 2;
return 3;
}
signed main (){
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int n;
cin>>n;
for (int i = 0; i <= n; i++)
for (int a=0;a<=3;a++)
for (int b=0;b<=3;b++)
for (int c=0;c<=3;c++)
for (int d=0;d<=3;d++)
dp[i][a][b][c][d] = -1;
dp[0][0][0][0][0] = 0;
for (int i = 1; i <= n; i++){
char ch;
cin>>ch;
int x = get(ch);
vector <pair<int,pair <pair <int,int>, pair<int,int> > > > vec;
for (int a = 0; a <= 3; a++)
for (int b = 0; b <= 3; b++)
for (int c = 0; c <= 3; c++)
for (int d = 0; d <= 3; d++){
if (dp[i-1][a][b][c][d] < 0) continue;
vec.pb({dp[i - 1][a][b][c][d] + getans(a,b,x),{{b,x},{c,d}}});
vec.pb({dp[i - 1][a][b][c][d] + getans(c,d,x),{{a,b},{d,x}}});
}
for(int j=0;j<(int)vec.size();j++){
int a = vec[j].s.f.f,b = vec[j].s.f.s;
int c = vec[j].s.s.f,d = vec[j].s.s.s;
dp[i][a][b][c][d] = max(dp[i][a][b][c][d],vec[j].f);
if (i == n) ans=max(ans,dp[i][a][b][c][d]);
}
}
cout<<ans;
}
# | 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... |