Submission #164133

#	Time	Username	Problem	Language	Result	Execution time	Memory
164133		toonewbie	Miners (IOI07_miners)	Java	100 / 100	1283 ms	13992 KiB

miners

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;
    }
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8