Submission #164123

#	Time	Username	Problem	Language	Result	Execution time	Memory
164123		toonewbie	Miners (IOI07_miners)	Java	0 / 100	1766 ms	137192 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[n][4][4][4][4][2];
        dp[0][0][0][0][0][0]=0;
        dp[0][0][0][0][0][1]=0;
        dp[1][0][arr[0]][0][0][0]=1+(arr[0]==arr[1]?1:2);
        dp[1][0][arr[0]][0][0][1]=2;
        dp[1][0][0][0][arr[0]][0]=2;
        dp[1][0][0][0][arr[0]][1]=1+(arr[0]==arr[1]?1:2);
        for(int i=1;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][j][k][p][d][u]!=0){
                                    int a=dp[i+1][j][k][d][arr[i]][1];
                                    int b=dp[i+1][k][arr[i]][p][d][0];
                                    if(u==0){
                                        dp[i+1][k][arr[i]][p][d][0]=Math.max(b,dp[i][j][k][p][d][u]+numEqual(k,arr[i],arr[i+1]));
                                        dp[i+1][k][arr[i]][p][d][1]=Math.max(b,dp[i][j][k][p][d][u]+numEqual(p,d,arr[i+1]));

                                    }
                                    if(u==1){
                                        dp[i+1][j][k][d][arr[i]][1]=Math.max(a,dp[i][j][k][p][d][u]+numEqual(d,arr[i],arr[i+1]));
                                        dp[i+1][j][k][d][arr[i]][0]=Math.max(a,dp[i][j][k][p][d][u]+numEqual(j,k,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++){
                            if(dp[n-1][j][k][p][d][u]>ans){
                                j=j;
                            }
                            ans=Math.max(ans,dp[n-1][j][k][p][d][u]);
                        }
                    }
                }
            }
        }//        ans=1+recurse(0,0,0,arr[0],0,0,0);
//        int b=1+recurse(0,0,0,0,0,0,arr[0]);
//        System.out.print(Math.max(ans,b));
        System.out.print(ans);
        f.close();
        out.close();
    }
    static int n;
    static int[]arr;
//    static int [][][][][][][]dp=new int[100002][4][4][4][4][4][4];
    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: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 7
• Subtask 7: 0 / 8
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8