Submission #1449956
Source Code Expand
import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.io.IOException; import java.io.InputStreamReader; import java.util.TreeSet; import java.util.StringTokenizer; import java.io.BufferedReader; import java.util.Comparator; import java.io.InputStream; /** * Built using CHelper plug-in * Actual solution is at the top */ public class Main { public static void main(String[] args) { InputStream inputStream = System.in; OutputStream outputStream = System.out; InputReader in = new InputReader(inputStream); PrintWriter out = new PrintWriter(outputStream); TaskC solver = new TaskC(); solver.solve(1, in, out); out.close(); } static class TaskC { static final long INF = (long) 1e18; private TreeSet<TaskC.Person>[][] queues; int[] togo; long[][] best; int[][] bestVia; public void solve(int testNumber, InputReader in, PrintWriter out) { togo = new int[3]; int n = 0; for (int i = 0; i < 3; ++i) { togo[i] = in.nextInt(); n += togo[i]; } TaskC.Person[] p = new TaskC.Person[n]; for (int i = 0; i < n; ++i) { p[i] = new TaskC.Person(); p[i].id = i; for (int j = 0; j < 3; ++j) p[i].cost[j] = in.nextInt(); } queues = new TreeSet[4][4]; for (int old = 0; old < 4; ++old) { for (int nxt = 0; nxt < 3; ++nxt) { if (nxt != old) { final int nxtCopy = nxt; final int oldCopy = old; queues[old][nxt] = new TreeSet<>(new Comparator<TaskC.Person>() { public int compare(TaskC.Person o1, TaskC.Person o2) { int z = (o2.cost[nxtCopy] - o2.cost[oldCopy]) - (o1.cost[nxtCopy] - o1.cost[oldCopy]); if (z == 0) z = o1.id - o2.id; return z; } }); } } } for (TaskC.Person pp : p) { for (int nxt = 0; nxt < 3; ++nxt) { queues[3][nxt].add(pp); } } best = new long[4][1 << 3]; bestVia = new int[4][1 << 3]; long res = 0; for (int i = 0; i < n; ++i) { int c = 3; int av = (1 << 3) - 1; for (long[] x : best) Arrays.fill(x, -INF); for (int[] x : bestVia) Arrays.fill(x, -2); rec(c, av); if (bestVia[c][av] < 0) throw new RuntimeException(); res += best[c][av]; while (true) { int d = bestVia[c][av]; if (d == -1) { --togo[c]; break; } TreeSet<TaskC.Person> q = queues[c][d]; TaskC.Person pp = q.first(); if (pp.now != c) throw new RuntimeException(); for (int nxt = 0; nxt < 3; ++nxt) if (queues[c][nxt] != null) queues[c][nxt].remove(pp); pp.now = d; for (int nxt = 0; nxt < 3; ++nxt) if (queues[d][nxt] != null) queues[d][nxt].add(pp); av ^= (1 << d); c = d; } } for (int x : togo) if (x != 0) throw new RuntimeException(); out.println(res); } private void rec(int c, int av) { if (c < 3) { if (togo[c] > 0) { best[c][av] = 0; bestVia[c][av] = -1; } } for (int cc = 0; cc < 3; ++cc) if ((av & (1 << cc)) != 0) { TreeSet<TaskC.Person> q = queues[c][cc]; if (q.isEmpty()) continue; TaskC.Person p = q.first(); if (bestVia[cc][av ^ (1 << cc)] == -2) rec(cc, av ^ (1 << cc)); long cur = p.cost[cc] - p.cost[c] + best[cc][av ^ (1 << cc)]; if (cur > best[c][av]) { best[c][av] = cur; bestVia[c][av] = cc; } } if (bestVia[c][av] == -2) bestVia[c][av] = -3; } static class Person { int id; int[] cost = new int[4]; int now = 3; } } 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 | C - Coins |
User | Petr |
Language | Java8 (OpenJDK 1.8.0) |
Score | 800 |
Code Size | 5647 Byte |
Status | AC |
Exec Time | 1014 ms |
Memory | 74092 KB |
Compile Error
Note: ./Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 800 / 800 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 73 ms | 21460 KB |
sample_02.txt | AC | 71 ms | 21460 KB |
sample_03.txt | AC | 72 ms | 19540 KB |
subtask_1_01.txt | AC | 71 ms | 23380 KB |
subtask_1_02.txt | AC | 304 ms | 32940 KB |
subtask_1_03.txt | AC | 493 ms | 45512 KB |
subtask_1_04.txt | AC | 585 ms | 49724 KB |
subtask_1_05.txt | AC | 578 ms | 50856 KB |
subtask_1_06.txt | AC | 673 ms | 47336 KB |
subtask_1_07.txt | AC | 378 ms | 33312 KB |
subtask_1_08.txt | AC | 711 ms | 47724 KB |
subtask_1_09.txt | AC | 311 ms | 35268 KB |
subtask_1_10.txt | AC | 638 ms | 49272 KB |
subtask_1_11.txt | AC | 854 ms | 58804 KB |
subtask_1_12.txt | AC | 750 ms | 73068 KB |
subtask_1_13.txt | AC | 831 ms | 74092 KB |
subtask_1_14.txt | AC | 747 ms | 59612 KB |
subtask_1_15.txt | AC | 787 ms | 57456 KB |
subtask_1_16.txt | AC | 753 ms | 53864 KB |
subtask_1_17.txt | AC | 796 ms | 56636 KB |
subtask_1_18.txt | AC | 822 ms | 58276 KB |
subtask_1_19.txt | AC | 847 ms | 57232 KB |
subtask_1_20.txt | AC | 818 ms | 59172 KB |
subtask_1_21.txt | AC | 812 ms | 71344 KB |
subtask_1_22.txt | AC | 788 ms | 70216 KB |
subtask_1_23.txt | AC | 760 ms | 59020 KB |
subtask_1_24.txt | AC | 775 ms | 62144 KB |
subtask_1_25.txt | AC | 753 ms | 54680 KB |
subtask_1_26.txt | AC | 1014 ms | 57420 KB |
subtask_1_27.txt | AC | 830 ms | 54264 KB |
subtask_1_28.txt | AC | 772 ms | 58808 KB |
subtask_1_29.txt | AC | 73 ms | 21460 KB |