| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 94909 |
2019-01-25T05:06:56 Z |
Retro3014 |
Miners (IOI07_miners) |
C++17 |
|
92 ms |
1144 KB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
using namespace std;
#define MAX_N 100000
#define INF 1000000000
int N;
string str;
int arr[MAX_N+1];
int dp1[4][4][4][4], dp2[4][4][4][4];
int main(){
scanf("%d", &N);
cin>>str;
for(int i=0; i<N; i++){
if(str[i]=='M') arr[i] = 1;
else if(str[i]=='F') arr[i] = 2;
else arr[i] = 3;
}
for(int i=0; i<4; i++){
for(int j=0; j<4; j++){
for(int k=0; k<4; k++){
for(int t=0; t<4; t++){
dp1[i][j][k][t] = -INF;
}
}
}
}
dp1[0][0][0][0] = 0;
for(int T=0; T<N; T++){
for(int i=0; i<4; i++){
for(int j=0; j<4; j++){
for(int k=0; k<4; k++){
for(int t=0; t<4; t++){
dp2[i][j][k][t] = -INF;
}
}
}
}
for(int i=0; i<4; i++){
for(int j=0; j<4; j++){
for(int k=0; k<4; k++){
for(int t=0; t<4; t++){
if(dp1[i][j][k][t]==-INF) continue;
if(k==0){
if(t==0){
dp2[i][j][0][arr[T]] = max(dp2[i][j][0][arr[T]], dp1[i][j][k][t]+1);
}
else if(t==arr[T]){
dp2[i][j][t][arr[T]] = max(dp2[i][j][t][arr[T]], dp1[i][j][k][t]+1);
}else{
dp2[i][j][t][arr[T]] = max(dp2[i][j][t][arr[T]], dp1[i][j][k][t]+2);
}
}else{
int cnt = 0;
cnt+=(k==t);
cnt+=(k==arr[T]);
cnt+=(t==arr[T]);
if(cnt==0){
dp2[i][j][t][arr[T]] = max(dp2[i][j][t][arr[T]], dp1[i][j][k][t]+3);
}else if(cnt==1){
dp2[i][j][t][arr[T]] = max(dp2[i][j][t][arr[T]], dp1[i][j][k][t]+2);
}else{
dp2[i][j][t][arr[T]] = max(dp2[i][j][t][arr[T]], dp1[i][j][k][t]+1);
}
}
if(i==0){
if(j==0){
dp2[0][arr[T]][k][t] = max(dp2[0][arr[T]][k][t], dp1[i][j][k][t]+1);
}else if(arr[T]==j){
dp2[j][arr[T]][k][t] = max(dp2[j][arr[T]][k][t], dp1[i][j][k][t]+1);
}else{
dp2[j][arr[T]][k][t] = max(dp2[j][arr[T]][k][t], dp1[i][j][k][t]+2);
}
}else{
int cnt = 0;
cnt+=(i==j);
cnt+=(i==arr[T]);
cnt+=(j==arr[T]);
if(cnt==0){
dp2[j][arr[T]][k][t] = max(dp2[j][arr[T]][k][t], dp1[i][j][k][t]+3);
}else if(cnt==1){
dp2[j][arr[T]][k][t] = max(dp2[j][arr[T]][k][t], dp1[i][j][k][t]+2);
}else{
dp2[j][arr[T]][k][t] = max(dp2[j][arr[T]][k][t], dp1[i][j][k][t]+1);
}
}
}
}
}
}
for(int i=0; i<4; i++){
for(int j=0; j<4; j++){
for(int k=0; k<4; k++){
for(int t=0; t<4; t++){
dp1[i][j][k][t] = dp2[i][j][k][t];
}
}
}
}
}
int ans = 0;
for(int i=0; i<4; i++){
for(int j=0; j<4; j++){
for(int k=0; k<4; k++){
for(int t=0; t<4; t++){
ans = max(ans, dp1[i][j][k][t]);
}
}
}
}
printf("%d", ans);
return 0;
}
Compilation message
miners.cpp: In function 'int main()':
miners.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
1144 KB |
Output is correct |
