Submission #691904
Source Code Expand
import static java.lang.Math.*; import static java.util.Arrays.*; import java.util.*; import java.io.*; public class Main { void solve() { int n = sc.nextInt(); long[] A = new long[n]; for (int i = 0; i < n; i++) A[i] = sc.nextLong(); long ans = HuTucker(A); out.println(ans); } long HuTucker(long[] A) { int N = A.length; SkewHeap[] hpq = new SkewHeap[N]; int[] rig = new int[N]; int[] lef = new int[N]; long[] cst = new long[N]; PriorityQueue<HuTuckerNode> mpq = new PriorityQueue<>(); for (int i = 0; i < N - 1; i++) { hpq[i] = null; rig[i] = i + 1; lef[i] = i - 1; cst[i] = A[i] + A[i + 1]; mpq.add(new HuTuckerNode(cst[i], i)); } long ans = 0; for (int step = 0; step < N - 1; step++) { int i; long c; do { HuTuckerNode top = mpq.poll(); c = top.w; i = top.pos; } while (rig[i] == -1 || cst[i] != c); boolean ml = false, mr = false; if (A[i] + fst(hpq[i]) == c) { hpq[i] = SkewHeap.pop(hpq[i]); ml = true; } else if (A[i] + A[rig[i]] == c) { ml = mr = true; } else if (fst(hpq[i]) + snd(hpq[i]) == c) { hpq[i] = SkewHeap.pop(SkewHeap.pop(hpq[i])); } else { hpq[i] = SkewHeap.pop(hpq[i]); mr = true; } ans += c; hpq[i] = SkewHeap.add(hpq[i], c); if (ml) A[i] = INF; if (mr)A[rig[i]] = INF; if (ml && i > 0) { int j = lef[i]; hpq[j] = SkewHeap.meld(hpq[j], hpq[i]); rig[j] = rig[i]; rig[i] = -1; lef[rig[j]] = j; i = j; } if (mr && rig[i] + 1 < N) { int j = rig[i]; hpq[i] = SkewHeap.meld(hpq[i], hpq[j]); rig[i] = rig[j]; rig[j] = -1; lef[rig[i]] = i; } cst[i] = A[i] + A[rig[i]]; cst[i] = min(cst[i], min(A[i], A[rig[i]]) + fst(hpq[i])); cst[i] = min(cst[i], fst(hpq[i]) + snd(hpq[i])); mpq.add(new HuTuckerNode(cst[i], i)); } return ans; } static final long INF = 1L << 58; long fst(SkewHeap p) { return p != null ? p.val : INF; } long snd(SkewHeap p) { return p != null ? min(fst(p.l), fst(p.r)) : INF; } class HuTuckerNode implements Comparable<HuTuckerNode> { long w; int pos; public HuTuckerNode(long w, int pos) { this.w = w; this.pos = pos; } @Override public int compareTo(HuTuckerNode o) { if (w != o.w) return w < o.w ? -1 : 1; return pos < o.pos ? -1 : 1; } } static class SkewHeap { SkewHeap l, r; long val; public SkewHeap(long val) { this.val = val; } static SkewHeap add(SkewHeap x, long val) { return meld(x, new SkewHeap(val)); } static SkewHeap pop(SkewHeap x) { return meld(x.l, x.r); } static SkewHeap meld(SkewHeap a, SkewHeap b) { if (a == null) return b; if (b == null) return a; if (a.val > b.val) { SkewHeap tmp = a;a = b;b = tmp; } a.r = meld(a.r, b); { SkewHeap tmp = a.l;a.l = a.r;a.r = tmp; } return a; } } static void tr(Object... os) { System.err.println(deepToString(os)); } static void tr(int[][] as) { for (int[] a : as) tr(a); } void print(int[] a) { out.print(a[0]); for (int i = 1; i < a.length; i++) out.print(" " + a[i]); out.println(); } public static void main(String[] args) throws Exception { new Main().run(); } MyScanner sc = null; PrintWriter out = null; public void run() throws Exception { sc = new MyScanner(System.in); out = new PrintWriter(System.out); for (;sc.hasNext();) { solve(); out.flush(); } out.close(); } class MyScanner { String line; BufferedReader reader; StringTokenizer tokenizer; public MyScanner(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream)); tokenizer = null; } public void eat() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { line = reader.readLine(); if (line == null) { tokenizer = null; return; } tokenizer = new StringTokenizer(line); } catch (IOException e) { throw new RuntimeException(e); } } } public String next() { eat(); return tokenizer.nextToken(); } public String nextLine() { try { return reader.readLine(); } catch (IOException e) { throw new RuntimeException(e); } } public boolean hasNext() { eat(); return (tokenizer != null && tokenizer.hasMoreElements()); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } public int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); return a; } } }
Submission Info
Submission Time | |
---|---|
Task | C - 最適二分探索木 |
User | hs484 |
Language | Java8 (OpenJDK 1.8.0) |
Score | 101 |
Code Size | 4776 Byte |
Status | AC |
Exec Time | 645 ms |
Memory | 29576 KB |
Judge Result
Set Name | Sample | Dataset1 | Dataset2 | Dataset3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 50 | 50 / 50 | 1 / 1 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_01.txt |
Dataset1 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt |
Dataset2 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt, 02_00.txt, 02_01.txt, 02_02.txt, 02_03.txt, 02_04.txt, 02_05.txt, 02_06.txt, 02_07.txt, 02_08.txt, 02_09.txt, 02_10.txt, 02_11.txt, 02_12.txt, 02_13.txt, 02_14.txt, 02_15.txt, 02_16.txt, 02_17.txt, 02_18.txt, 02_19.txt, 02_20.txt, 02_21.txt, 02_22.txt, 02_23.txt, 02_24.txt, 02_25.txt, 02_26.txt, 02_27.txt, 02_28.txt, 02_29.txt |
Dataset3 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt, 02_00.txt, 02_01.txt, 02_02.txt, 02_03.txt, 02_04.txt, 02_05.txt, 02_06.txt, 02_07.txt, 02_08.txt, 02_09.txt, 02_10.txt, 02_11.txt, 02_12.txt, 02_13.txt, 02_14.txt, 02_15.txt, 02_16.txt, 02_17.txt, 02_18.txt, 02_19.txt, 02_20.txt, 02_21.txt, 02_22.txt, 02_23.txt, 02_24.txt, 02_25.txt, 02_26.txt, 02_27.txt, 02_28.txt, 02_29.txt, 03_00.txt, 03_01.txt, 03_02.txt, 03_03.txt, 03_04.txt, 03_05.txt, 03_06.txt, 03_07.txt, 03_08.txt, 03_09.txt, 03_10.txt, 03_11.txt, 03_12.txt, 03_13.txt, 03_14.txt, 03_15.txt, 03_16.txt, 03_17.txt, 03_18.txt, 03_19.txt, 03_20.txt, 03_21.txt, 03_22.txt, 03_23.txt, 03_24.txt, 03_25.txt, 03_26.txt, 03_27.txt, 03_28.txt, 03_29.txt, 03_30.txt, 03_31.txt, 03_32.txt, 03_33.txt, 03_34.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01.txt | AC | 161 ms | 8276 KB |
01_00.txt | AC | 165 ms | 8144 KB |
01_01.txt | AC | 162 ms | 8148 KB |
01_02.txt | AC | 163 ms | 8272 KB |
01_03.txt | AC | 164 ms | 8148 KB |
01_04.txt | AC | 159 ms | 8148 KB |
01_05.txt | AC | 153 ms | 8276 KB |
01_06.txt | AC | 154 ms | 8144 KB |
01_07.txt | AC | 158 ms | 8276 KB |
01_08.txt | AC | 160 ms | 8144 KB |
01_09.txt | AC | 161 ms | 8276 KB |
01_10.txt | AC | 155 ms | 8276 KB |
01_11.txt | AC | 163 ms | 8144 KB |
01_12.txt | AC | 154 ms | 8276 KB |
01_13.txt | AC | 163 ms | 8148 KB |
01_14.txt | AC | 167 ms | 8148 KB |
01_15.txt | AC | 156 ms | 8276 KB |
01_16.txt | AC | 156 ms | 8272 KB |
01_17.txt | AC | 156 ms | 8276 KB |
01_18.txt | AC | 165 ms | 8144 KB |
01_19.txt | AC | 164 ms | 8148 KB |
01_20.txt | AC | 155 ms | 8144 KB |
01_21.txt | AC | 156 ms | 8276 KB |
01_22.txt | AC | 152 ms | 8148 KB |
01_23.txt | AC | 156 ms | 8148 KB |
01_24.txt | AC | 161 ms | 8276 KB |
01_25.txt | AC | 168 ms | 8144 KB |
01_26.txt | AC | 157 ms | 8148 KB |
01_27.txt | AC | 160 ms | 8272 KB |
01_28.txt | AC | 163 ms | 8276 KB |
01_29.txt | AC | 160 ms | 8148 KB |
02_00.txt | AC | 200 ms | 9300 KB |
02_01.txt | AC | 197 ms | 9428 KB |
02_02.txt | AC | 201 ms | 9428 KB |
02_03.txt | AC | 193 ms | 9300 KB |
02_04.txt | AC | 199 ms | 9300 KB |
02_05.txt | AC | 201 ms | 9428 KB |
02_06.txt | AC | 199 ms | 9428 KB |
02_07.txt | AC | 207 ms | 9300 KB |
02_08.txt | AC | 207 ms | 9428 KB |
02_09.txt | AC | 199 ms | 9296 KB |
02_10.txt | AC | 211 ms | 9428 KB |
02_11.txt | AC | 231 ms | 9172 KB |
02_12.txt | AC | 207 ms | 9428 KB |
02_13.txt | AC | 201 ms | 9360 KB |
02_14.txt | AC | 198 ms | 9428 KB |
02_15.txt | AC | 194 ms | 9300 KB |
02_16.txt | AC | 195 ms | 9300 KB |
02_17.txt | AC | 205 ms | 9428 KB |
02_18.txt | AC | 201 ms | 9300 KB |
02_19.txt | AC | 207 ms | 9428 KB |
02_20.txt | AC | 188 ms | 9296 KB |
02_21.txt | AC | 208 ms | 9364 KB |
02_22.txt | AC | 209 ms | 9300 KB |
02_23.txt | AC | 200 ms | 9296 KB |
02_24.txt | AC | 203 ms | 9300 KB |
02_25.txt | AC | 206 ms | 9428 KB |
02_26.txt | AC | 192 ms | 9428 KB |
02_27.txt | AC | 199 ms | 9424 KB |
02_28.txt | AC | 206 ms | 9428 KB |
02_29.txt | AC | 203 ms | 9428 KB |
03_00.txt | AC | 600 ms | 29192 KB |
03_01.txt | AC | 623 ms | 28596 KB |
03_02.txt | AC | 645 ms | 29288 KB |
03_03.txt | AC | 571 ms | 29304 KB |
03_04.txt | AC | 593 ms | 28952 KB |
03_05.txt | AC | 597 ms | 29016 KB |
03_06.txt | AC | 603 ms | 29356 KB |
03_07.txt | AC | 558 ms | 28916 KB |
03_08.txt | AC | 611 ms | 28836 KB |
03_09.txt | AC | 556 ms | 29220 KB |
03_10.txt | AC | 582 ms | 29280 KB |
03_11.txt | AC | 504 ms | 27460 KB |
03_12.txt | AC | 524 ms | 29036 KB |
03_13.txt | AC | 521 ms | 29116 KB |
03_14.txt | AC | 643 ms | 29480 KB |
03_15.txt | AC | 479 ms | 28584 KB |
03_16.txt | AC | 570 ms | 29256 KB |
03_17.txt | AC | 584 ms | 29044 KB |
03_18.txt | AC | 571 ms | 28588 KB |
03_19.txt | AC | 555 ms | 29072 KB |
03_20.txt | AC | 534 ms | 29224 KB |
03_21.txt | AC | 568 ms | 28524 KB |
03_22.txt | AC | 562 ms | 29212 KB |
03_23.txt | AC | 561 ms | 27972 KB |
03_24.txt | AC | 572 ms | 29256 KB |
03_25.txt | AC | 580 ms | 29200 KB |
03_26.txt | AC | 555 ms | 28944 KB |
03_27.txt | AC | 508 ms | 28996 KB |
03_28.txt | AC | 591 ms | 29268 KB |
03_29.txt | AC | 603 ms | 29576 KB |
03_30.txt | AC | 551 ms | 28860 KB |
03_31.txt | AC | 526 ms | 28904 KB |
03_32.txt | AC | 611 ms | 28344 KB |
03_33.txt | AC | 559 ms | 28820 KB |
03_34.txt | AC | 575 ms | 28928 KB |