Submission #692404
Source Code Expand
import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; public class Main { static InputStream is; static PrintWriter out; static String INPUT = ""; static void solve() { int n = ni(); int[] a = na(n); if(n == 1){ out.println(0); return; } OBST2 o = new OBST2(a); o.go(); long w = 0; for(int i = n;i < 2*n-1;i++){ w += o.w[i]; } out.println(w); } public static class OBST2 { public int[] w; public int[] l, r; public int[] d; public int[] q; public int[] v; public int t, m, n; public OBST2(int[] a) { n = a.length; m = n-1; w = new int[2*n-1]; l = new int[2*n-1]; r = new int[2*n-1]; Arrays.fill(l, -1); Arrays.fill(r, -1); d = new int[2*n-1]; q = new int[2*n-1]; v = new int[2*n-1]; for(int i = 0;i < a.length;i++){ this.w[i] = a[i]; } } public void combine(int k) { m++; l[m] = v[k-1]; r[m] = v[k]; int x = q[k-1] + q[k]; w[m] = x; t--; for(int j = k;j <= t;j++){ q[j] = q[j+1]; v[j] = v[j+1]; } int j; for(j = k-2;q[j] < x;j--){ q[j+1] = q[j]; v[j+1] = v[j]; } q[j+1] = x; v[j+1] = m; while(j > 0 && q[j-1] <= x){ int dum = t-j; combine(j); j = t-dum; } } void mark(int k, int p) { d[k] = p; if(l[k] >= 0)mark(l[k], p+1); if(r[k] >= 0)mark(r[k], p+1); } void build(int b){ int j = m; if(d[t] == b){ l[j] = t++; }else{ m--; l[j] = m; build(b+1); } if(d[t] == b){ r[j] = t++; }else{ m--; r[j] = m; build(b+1); } } public void go() { t = 1; q[0] = 1000000007; q[1] = w[0]; v[1] = 0; for(int k = 1;k <= n-1;k++){ while(q[t-1] <= w[k])combine(t); t++; q[t] = w[k]; v[t] = k; } while(t > 1)combine(t); mark(v[1], 0); t = 0; m = 2*(n-1); build(1); } } public static void main(String[] args) throws Exception { long S = System.currentTimeMillis(); is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); solve(); out.flush(); long G = System.currentTimeMillis(); tr(G-S+"ms"); } private static boolean eof() { if(lenbuf == -1)return true; int lptr = ptrbuf; while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false; try { is.mark(1000); while(true){ int b = is.read(); if(b == -1){ is.reset(); return true; }else if(!isSpaceChar(b)){ is.reset(); return false; } } } catch (IOException e) { return true; } } private static byte[] inbuf = new byte[1024]; static int lenbuf = 0, ptrbuf = 0; private static int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } // private static boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); } private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private static double nd() { return Double.parseDouble(ns()); } private static char nc() { return (char)skip(); } private static String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private static char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private static char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private static int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private static int ni() { int num = 0, b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); } }
Submission Info
Submission Time | |
---|---|
Task | C - 最適二分探索木 |
User | uwi |
Language | Java8 (OpenJDK 1.8.0) |
Score | 101 |
Code Size | 5216 Byte |
Status | AC |
Exec Time | 432 ms |
Memory | 16028 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 | 152 ms | 7892 KB |
01_00.txt | AC | 152 ms | 7892 KB |
01_01.txt | AC | 153 ms | 7892 KB |
01_02.txt | AC | 155 ms | 7888 KB |
01_03.txt | AC | 149 ms | 7892 KB |
01_04.txt | AC | 148 ms | 8020 KB |
01_05.txt | AC | 148 ms | 7888 KB |
01_06.txt | AC | 152 ms | 7888 KB |
01_07.txt | AC | 147 ms | 7892 KB |
01_08.txt | AC | 160 ms | 7892 KB |
01_09.txt | AC | 157 ms | 7892 KB |
01_10.txt | AC | 153 ms | 7892 KB |
01_11.txt | AC | 157 ms | 7892 KB |
01_12.txt | AC | 159 ms | 7888 KB |
01_13.txt | AC | 148 ms | 8020 KB |
01_14.txt | AC | 148 ms | 7892 KB |
01_15.txt | AC | 159 ms | 7892 KB |
01_16.txt | AC | 157 ms | 7888 KB |
01_17.txt | AC | 148 ms | 7892 KB |
01_18.txt | AC | 157 ms | 7892 KB |
01_19.txt | AC | 160 ms | 8016 KB |
01_20.txt | AC | 158 ms | 7892 KB |
01_21.txt | AC | 156 ms | 7892 KB |
01_22.txt | AC | 163 ms | 8020 KB |
01_23.txt | AC | 159 ms | 7764 KB |
01_24.txt | AC | 156 ms | 7892 KB |
01_25.txt | AC | 154 ms | 7892 KB |
01_26.txt | AC | 150 ms | 7888 KB |
01_27.txt | AC | 148 ms | 7888 KB |
01_28.txt | AC | 157 ms | 7892 KB |
01_29.txt | AC | 149 ms | 7892 KB |
02_00.txt | AC | 168 ms | 8656 KB |
02_01.txt | AC | 171 ms | 8404 KB |
02_02.txt | AC | 179 ms | 8532 KB |
02_03.txt | AC | 162 ms | 8528 KB |
02_04.txt | AC | 174 ms | 8656 KB |
02_05.txt | AC | 168 ms | 8652 KB |
02_06.txt | AC | 172 ms | 8820 KB |
02_07.txt | AC | 180 ms | 8784 KB |
02_08.txt | AC | 178 ms | 9036 KB |
02_09.txt | AC | 177 ms | 8724 KB |
02_10.txt | AC | 174 ms | 8656 KB |
02_11.txt | AC | 212 ms | 8656 KB |
02_12.txt | AC | 169 ms | 8784 KB |
02_13.txt | AC | 166 ms | 8404 KB |
02_14.txt | AC | 168 ms | 8916 KB |
02_15.txt | AC | 183 ms | 8916 KB |
02_16.txt | AC | 176 ms | 8980 KB |
02_17.txt | AC | 178 ms | 8916 KB |
02_18.txt | AC | 172 ms | 8532 KB |
02_19.txt | AC | 162 ms | 8884 KB |
02_20.txt | AC | 168 ms | 8944 KB |
02_21.txt | AC | 166 ms | 8660 KB |
02_22.txt | AC | 179 ms | 8720 KB |
02_23.txt | AC | 176 ms | 8916 KB |
02_24.txt | AC | 172 ms | 8884 KB |
02_25.txt | AC | 178 ms | 8852 KB |
02_26.txt | AC | 175 ms | 8968 KB |
02_27.txt | AC | 169 ms | 8660 KB |
02_28.txt | AC | 171 ms | 8788 KB |
02_29.txt | AC | 169 ms | 8852 KB |
03_00.txt | AC | 325 ms | 15728 KB |
03_01.txt | AC | 313 ms | 15916 KB |
03_02.txt | AC | 327 ms | 15852 KB |
03_03.txt | AC | 316 ms | 15900 KB |
03_04.txt | AC | 316 ms | 15900 KB |
03_05.txt | AC | 215 ms | 15144 KB |
03_06.txt | AC | 322 ms | 15244 KB |
03_07.txt | AC | 306 ms | 15224 KB |
03_08.txt | AC | 276 ms | 15052 KB |
03_09.txt | AC | 268 ms | 15160 KB |
03_10.txt | AC | 271 ms | 15060 KB |
03_11.txt | AC | 255 ms | 15372 KB |
03_12.txt | AC | 302 ms | 15156 KB |
03_13.txt | AC | 319 ms | 15416 KB |
03_14.txt | AC | 263 ms | 15712 KB |
03_15.txt | AC | 259 ms | 15776 KB |
03_16.txt | AC | 323 ms | 15272 KB |
03_17.txt | AC | 432 ms | 15588 KB |
03_18.txt | AC | 268 ms | 15272 KB |
03_19.txt | AC | 296 ms | 15152 KB |
03_20.txt | AC | 269 ms | 15928 KB |
03_21.txt | AC | 265 ms | 15596 KB |
03_22.txt | AC | 262 ms | 15816 KB |
03_23.txt | AC | 394 ms | 15584 KB |
03_24.txt | AC | 270 ms | 15324 KB |
03_25.txt | AC | 304 ms | 15148 KB |
03_26.txt | AC | 282 ms | 15040 KB |
03_27.txt | AC | 258 ms | 15716 KB |
03_28.txt | AC | 259 ms | 15884 KB |
03_29.txt | AC | 420 ms | 15316 KB |
03_30.txt | AC | 312 ms | 15196 KB |
03_31.txt | AC | 268 ms | 16028 KB |
03_32.txt | AC | 265 ms | 15784 KB |
03_33.txt | AC | 268 ms | 15936 KB |
03_34.txt | AC | 267 ms | 15768 KB |