Submission #263648

#TimeUsernameProblemLanguageResultExecution timeMemory
263648updown1Miners (IOI07_miners)Java
76 / 100
1949 ms227916 KiB
import java.util.*;
import java.io.*;
public class miners {
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(bf.readLine());
        String[] food = bf.readLine().split("");
        int[][][] dp = new int[N+2][34][34];
        int[] combos = new int[]{0, 1, 2, 3, 11, 12, 13, 21, 22, 23, 31, 32, 33};
        //1 = Meat, 2 = Fish, 3 = Bread
        for(int i = 0; i < 13; i++){
            for(int c = 0; c < 13; c++){
                dp[N+1][combos[i]][combos[c]] = 0;
            }
        }
        for(int i = N; i > 0; i--){
          int f = -1;
                    if(food[i-1].equals("M"))f = 1;
                    if(food[i-1].equals("F"))f = 2;
                    if(food[i-1].equals("B"))f = 3;
            for(int s1 = 0; s1 < 13; s1++){
                for(int s2 = 0; s2 < 13; s2++){
                    
                    int ns1 = (combos[s1]%10)*10 + f;
                    int ns2 = (combos[s2]%10)*10 + f;
                    if(combos[s1] == 0)ns1 = f;
                    if(combos[s2] == 0)ns2 = f;
                    dp[i][combos[s1]][combos[s2]] = Math.max(dp[i+1][ns1][combos[s2]] + value(combos[s1], f), dp[i+1][combos[s1]][ns2] + value(combos[s2], f));
                    //System.out.println("(" + i + ", " + combos[s1] + ", " + combos[s2] + ") = " + dp[i][combos[s1]][combos[s2]]);
                }
            }
        }
        pw.println(dp[1][0][0]);
        pw.close();
    }
    public static int value(int state, int f){
        int s = -1;
        if(state == 0)s = f;
        else s = state*10 + f;

        int[] v = {100, 100, 100};
        boolean print = false;
        //if (state == 31) print = true;
        if (print) System.out.println(state);
        while(s != 0){
            int num = s%10;
            s /= 10;
            if (v[0] == 100) v[0] = num;
            else if (v[1] == 100) v[1] = num;
            else v[2] = num;
            //count.add(num);
            
        }
        Arrays.sort(v);
        if (print) System.out.println(v[0] + " " + v[1] + " " + v[2]);
        int ret = 1;
        if (v[1] != v[0] && v[1] != 100) ret++;
        if (v[2] != v[1] && v[2] != 100) ret++;
        if (print) {System.out.println(ret); System.out.println();}
        return ret;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...