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
AC × 1
AC × 31
AC × 61
AC × 96
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