| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 164133 |
2019-11-17T14:57:37 Z |
toonewbie |
Miners (IOI07_miners) |
Java 11 |
|
1283 ms |
13992 KB |
import java.util.*;
import java.io.*;
public class miners {
public static void main(String[] args) throws IOException{
BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new PrintStream(System.out));
n=Integer.parseInt(f.readLine());
char[]atem=f.readLine().toCharArray();
arr=new int[n];
for(int i=0;i<n;i++){
if(atem[i]=='M'){
arr[i]=1;
}
else if(atem[i]=='F'){
arr[i]=2;
}
else{
arr[i]=3;
}
}
int dp[][][][][][]=new int[2][4][4][4][4][2];
dp[0][0][arr[0]][0][0][0] = 1;
dp[0][0][0][0][arr[0]][1] = 1;
for(int i=0;i<n-1;i++){
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
for(int p=0;p<4;p++){
for(int d=0;d<4;d++){
for(int u=0;u<2;u++){
if(dp[i&1][j][k][p][d][u]!=0){
int x = dp[i&1][j][k][p][d][u];
dp[(i + 1)&1][k][arr[i + 1]][p][d][0] = Math.max(dp[(i + 1)&1][k][arr[i + 1]][p][d][0], x + numEqual(j, k, arr[i + 1]));
dp[(i + 1)&1][j][k][d][arr[i + 1]][1] = Math.max(dp[(i + 1)&1][j][k][d][arr[i + 1]][1], x + numEqual(p, d, arr[i + 1]));
}
}
}
}
}
}
}
int ans=0;
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
for(int p=0;p<4;p++){
for(int d=0;d<4;d++){
for(int u=0;u<2;u++){
ans=Math.max(ans,dp[(n-1)&1][j][k][p][d][u]);
}
}
}
}
}
System.out.print(ans);
f.close();
out.close();
}
static int n;
static int[]arr;
static int recurse(int idx,int l1,int l2,int l3,int r1, int r2,int r3){
int max=0;
if(idx==-1+n)return 0;
//choose left
int val=numEqual(l2,l3,arr[idx+1]);
val+=recurse(idx+1,l2,l3,arr[idx+1],r1,r2,r3);
max=Math.max(max,val);
val=numEqual(r2,r3,arr[idx+1]);
val+=recurse(idx+1,l1,l2,l3,r2,r3,arr[idx+1]);
max=Math.max(max,val);
return max;
}
static int numEqual(int a, int b, int c){
if(a==0 && b==0 && c==0)return 0;
if(a==0 && b==0)return 1;
if(a==0){
return b==c?1:2;
}
if(a==b && b==c)
return 1;
if(a==b)
return 2;
if(b==c)
return 2;
if(a==c)return 2;
return 3;
}
}
class pair implements Comparable <pair>{
int num;
int idx;
public int compareTo(pair other){
return num- other.num;
}
pair(int a, int b)
{
num=a;
idx=b;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
9640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
9700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
9696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
9776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
9712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
9772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
140 ms |
11232 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
167 ms |
11924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
244 ms |
11956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
445 ms |
12096 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
945 ms |
13812 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1283 ms |
13992 KB |
Output is correct |
