Submission #163895

#	Time	Username	Problem	Language	Result	Execution time	Memory
163895		fluffypotato	Miners (IOI07_miners)	Java	45 / 100	1596 ms	22628 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 ans=0;
        ans=1+recurse(0,-1,-1,arr[0],-1,-1,-1);
        int b=1+recurse(0,-1,-1,-1,-1,-1,arr[0]);
        System.out.print(Math.max(ans,b));
        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==-1 && b==-1 && c==-1)return 0;
        if(a==-1 && b==-1)return 1;
        if(a==-1){
            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: 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