Submission #998695
Source Code Expand
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { InputReader in = new InputReader(System.in); PrintWriter out = new PrintWriter(System.out); Task task = new Task(in, out); task.solve(); out.close(); } static class Task { private InputReader in; private PrintWriter out; public Task(InputReader in, PrintWriter out) { this.in = in; this.out = out; } public void solve() { int K = in.nextInt(); String S = in.next(); int ssl = S.length() / (K+1); int sslp1 = S.length() - (K+1) * ssl; String[][] T = new String[S.length()][sslp1+1]; T[ssl-1][0] = S.substring(0, ssl); if (sslp1 > 0) T[ssl][1] = S.substring(0, ssl+1); for (int j = ssl+1; j < S.length(); j++) { // T[j][k] = best splitting of chars from 0-j in k strings of length sslp1 for (int k = 0; k <= sslp1; k++) { // cut j-(j-sslp1) if (k > 0 && j-ssl >= 0) T[j][k] = max(S.substring(j-ssl, j+1), table(T, j-ssl-1, k-1)); // cut j-(j-sslp1+1) if (j-ssl+1 >= 0) T[j][k] = min(T[j][k], max(S.substring(j-ssl+1, j+1), table(T, j-ssl, k))); } } out.println(T[S.length() - 1][sslp1]); } private String table(String[][] T, int j, int k) { if (j < 0 || k < 0) return null; return T[j][k]; } private String min(String a, String b) { if (a == null) return b; if (b == null) return a; if (a.length() < b.length()) return a; if (a.length() > b.length()) return b; return a.compareTo(b) < 0 ? a : b; } private String max(String a, String b) { if (a == null || b == null) return null; if (a.length() < b.length()) return b; if (a.length() > b.length()) return a; return a.compareTo(b) > 0 ? a : b; } } static class InputReader { public BufferedReader reader; public StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream), 32768); tokenizer = null; } public String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } public int nextInt() { return Integer.parseInt(next()); } } }
Submission Info
Submission Time | |
---|---|
Task | B - Problem where Commas Separate Digits |
User | chal |
Language | Java8 (OpenJDK 1.8.0) |
Score | 0 |
Code Size | 3201 Byte |
Status | WA |
Exec Time | 3206 ms |
Memory | 925396 KB |
Judge Result
Set Name | Sample | Dataset1 | Dataset2 | Dataset3 | Dataset4 | Dataset5 | ||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | 0 / 100 | 0 / 200 | 0 / 200 | 0 / 400 | ||||||||||||||||||||||||||
Status |
|
|
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask_02_ex1.txt, subtask_03_ex2.txt, subtask_03_ex3.txt |
Dataset1 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt |
Dataset2 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt |
Dataset3 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt |
Dataset4 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt, subtask_04_01.txt, subtask_04_02.txt, subtask_04_03.txt, subtask_04_04.txt, subtask_04_05.txt, subtask_04_06.txt, subtask_04_07.txt, subtask_04_08.txt, subtask_04_09.txt, subtask_04_10.txt, subtask_04_11.txt, subtask_04_12.txt, subtask_04_13.txt, subtask_04_14.txt, subtask_04_15.txt |
Dataset5 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt, subtask_04_01.txt, subtask_04_02.txt, subtask_04_03.txt, subtask_04_04.txt, subtask_04_05.txt, subtask_04_06.txt, subtask_04_07.txt, subtask_04_08.txt, subtask_04_09.txt, subtask_04_10.txt, subtask_04_11.txt, subtask_04_12.txt, subtask_04_13.txt, subtask_04_14.txt, subtask_04_15.txt, subtask_05_01.txt, subtask_05_02.txt, subtask_05_03.txt, subtask_05_04.txt, subtask_05_05.txt, subtask_05_06.txt, subtask_05_07.txt, subtask_05_08.txt, subtask_05_09.txt, subtask_05_10.txt, subtask_05_11.txt, subtask_05_12.txt, subtask_05_13.txt, subtask_05_14.txt, subtask_05_15.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask_01_01.txt | AC | 97 ms | 8400 KB |
subtask_01_02.txt | WA | 101 ms | 8400 KB |
subtask_01_03.txt | WA | 98 ms | 8400 KB |
subtask_01_04.txt | AC | 96 ms | 8404 KB |
subtask_01_05.txt | AC | 98 ms | 8528 KB |
subtask_01_06.txt | AC | 97 ms | 8400 KB |
subtask_01_07.txt | AC | 96 ms | 8532 KB |
subtask_01_08.txt | WA | 97 ms | 8400 KB |
subtask_01_09.txt | AC | 95 ms | 8400 KB |
subtask_01_10.txt | AC | 95 ms | 8532 KB |
subtask_01_11.txt | AC | 96 ms | 8400 KB |
subtask_01_12.txt | AC | 96 ms | 8404 KB |
subtask_01_13.txt | WA | 96 ms | 8404 KB |
subtask_01_14.txt | AC | 96 ms | 8404 KB |
subtask_01_15.txt | WA | 97 ms | 8400 KB |
subtask_01_16.txt | AC | 97 ms | 8400 KB |
subtask_01_17.txt | AC | 95 ms | 8404 KB |
subtask_02_01.txt | AC | 96 ms | 8400 KB |
subtask_02_02.txt | WA | 102 ms | 8528 KB |
subtask_02_03.txt | WA | 96 ms | 8528 KB |
subtask_02_04.txt | AC | 98 ms | 8400 KB |
subtask_02_05.txt | AC | 98 ms | 8528 KB |
subtask_02_06.txt | AC | 98 ms | 8528 KB |
subtask_02_07.txt | AC | 97 ms | 8528 KB |
subtask_02_08.txt | AC | 96 ms | 8532 KB |
subtask_02_09.txt | AC | 95 ms | 8404 KB |
subtask_02_10.txt | AC | 111 ms | 8532 KB |
subtask_02_11.txt | AC | 97 ms | 8524 KB |
subtask_02_12.txt | AC | 98 ms | 8400 KB |
subtask_02_13.txt | WA | 96 ms | 8400 KB |
subtask_02_14.txt | AC | 96 ms | 8400 KB |
subtask_02_ex1.txt | AC | 97 ms | 8404 KB |
subtask_03_01.txt | AC | 115 ms | 8784 KB |
subtask_03_02.txt | AC | 99 ms | 8660 KB |
subtask_03_03.txt | WA | 98 ms | 8528 KB |
subtask_03_04.txt | AC | 97 ms | 8404 KB |
subtask_03_05.txt | AC | 105 ms | 8784 KB |
subtask_03_06.txt | AC | 98 ms | 8528 KB |
subtask_03_07.txt | AC | 96 ms | 8528 KB |
subtask_03_08.txt | AC | 106 ms | 8532 KB |
subtask_03_09.txt | AC | 97 ms | 8528 KB |
subtask_03_10.txt | AC | 99 ms | 8660 KB |
subtask_03_11.txt | AC | 101 ms | 8656 KB |
subtask_03_12.txt | AC | 101 ms | 8784 KB |
subtask_03_13.txt | AC | 99 ms | 8532 KB |
subtask_03_14.txt | AC | 100 ms | 8528 KB |
subtask_03_15.txt | AC | 96 ms | 8396 KB |
subtask_03_ex2.txt | AC | 96 ms | 8404 KB |
subtask_03_ex3.txt | AC | 99 ms | 8532 KB |
subtask_04_01.txt | WA | 247 ms | 50288 KB |
subtask_04_02.txt | AC | 163 ms | 22052 KB |
subtask_04_03.txt | WA | 101 ms | 8656 KB |
subtask_04_04.txt | AC | 100 ms | 8528 KB |
subtask_04_05.txt | AC | 268 ms | 54644 KB |
subtask_04_06.txt | AC | 101 ms | 8656 KB |
subtask_04_07.txt | AC | 101 ms | 8656 KB |
subtask_04_08.txt | AC | 102 ms | 10576 KB |
subtask_04_09.txt | AC | 98 ms | 8528 KB |
subtask_04_10.txt | AC | 254 ms | 50424 KB |
subtask_04_11.txt | AC | 245 ms | 50148 KB |
subtask_04_12.txt | AC | 269 ms | 50512 KB |
subtask_04_13.txt | AC | 114 ms | 9936 KB |
subtask_04_14.txt | AC | 121 ms | 11216 KB |
subtask_04_15.txt | AC | 183 ms | 26604 KB |
subtask_05_01.txt | TLE | 3206 ms | 907868 KB |
subtask_05_02.txt | TLE | 3203 ms | 918012 KB |
subtask_05_03.txt | WA | 165 ms | 18720 KB |
subtask_05_04.txt | AC | 163 ms | 18720 KB |
subtask_05_05.txt | TLE | 3091 ms | 925396 KB |
subtask_05_06.txt | AC | 159 ms | 18652 KB |
subtask_05_07.txt | AC | 160 ms | 19612 KB |
subtask_05_08.txt | MLE | 1061 ms | 326968 KB |
subtask_05_09.txt | AC | 127 ms | 13776 KB |
subtask_05_10.txt | TLE | 3048 ms | 890116 KB |
subtask_05_11.txt | TLE | 3202 ms | 899924 KB |
subtask_05_12.txt | TLE | 3202 ms | 900040 KB |
subtask_05_13.txt | TLE | 3195 ms | 723972 KB |
subtask_05_14.txt | TLE | 3204 ms | 919956 KB |
subtask_05_15.txt | TLE | 3206 ms | 921092 KB |