# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
263752 |
2020-08-14T01:49:48 Z |
updown1 |
Miners (IOI07_miners) |
Java 11 |
|
1500 ms |
225148 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));
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]]);
}
}
}
System.out.println(dp[1][0][0]);
}
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;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
10528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
10868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
10464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
80 ms |
10352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
94 ms |
10608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
10488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
124 ms |
16152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
206 ms |
38172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
461 ms |
80004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1374 ms |
225148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1749 ms |
126028 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1810 ms |
190748 KB |
Time limit exceeded |