oj.uz

Submission #263726

# Submission time Handle Problem Language Result Execution time Memory
263726 2020-08-14T01:32:41 Z updown1 Miners (IOI07_miners) Java 11
84 / 100
 1500 ms 224644 KB 
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};
        int[][] store = new int[100][5];

        int[][] go = new int[13][5];

        for (int i=0; i<100; i++) for (int j=0; j<5; j++) store[i][j] = value(i, j);

        for (int i=0; i<13; i++) for (int j=0; j<5; j++) go[i][j] = (combos[i]%10)*10 + j;

        //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;
          else if(food[i-1].equals("F"))f = 2;
          else f = 3;
            for(int s1 = 0; s1 < 13; s1++){
              int ns1 = go[s1][f];
              int vs1 = store[combos[s1]][f];
                for(int s2 = 0; s2 < 13; s2++){
                    
                    
                    int ns2 = go[s2][f];

                    dp[i][combos[s1]][combos[s2]] = Math.max(dp[i+1][ns1][combos[s2]] + vs1, dp[i+1][combos[s1]][ns2] + store[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;
        s = state*10 + f;

        int[] v = new int[10];
        while(s != 0){
            int num = s%10;
            s /= 10;
            v[num]++;
        }
        int ret = 0;
        for (int i=0; i<10; i++) {
          if (v[i] > 0) ret++;
        }
        return ret;
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 10628 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 10596 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 10532 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 10476 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 10612 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 10616 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 16448 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 38272 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 80124 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1333 ms 224644 KB Output is correct

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1955 ms 124608 KB Time limit exceeded

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1973 ms 126116 KB Time limit exceeded