結果
問題 | No.448 ゆきこーだーの雨と雪 (3) |
ユーザー | ぴろず |
提出日時 | 2016-11-19 00:43:11 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 664 ms / 2,000 ms |
コード長 | 7,730 bytes |
コンパイル時間 | 3,113 ms |
コンパイル使用メモリ | 78,972 KB |
実行使用メモリ | 86,256 KB |
最終ジャッジ日時 | 2023-09-02 12:54:08 |
合計ジャッジ時間 | 17,796 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 57 ms
51,044 KB |
testcase_01 | AC | 56 ms
51,060 KB |
testcase_02 | AC | 50 ms
49,592 KB |
testcase_03 | AC | 53 ms
49,512 KB |
testcase_04 | AC | 75 ms
51,292 KB |
testcase_05 | AC | 76 ms
51,380 KB |
testcase_06 | AC | 71 ms
51,496 KB |
testcase_07 | AC | 69 ms
50,808 KB |
testcase_08 | AC | 67 ms
50,980 KB |
testcase_09 | AC | 78 ms
50,972 KB |
testcase_10 | AC | 68 ms
51,264 KB |
testcase_11 | AC | 77 ms
51,108 KB |
testcase_12 | AC | 75 ms
51,052 KB |
testcase_13 | AC | 215 ms
57,660 KB |
testcase_14 | AC | 215 ms
57,540 KB |
testcase_15 | AC | 377 ms
63,068 KB |
testcase_16 | AC | 489 ms
66,016 KB |
testcase_17 | AC | 536 ms
77,080 KB |
testcase_18 | AC | 192 ms
57,664 KB |
testcase_19 | AC | 561 ms
79,268 KB |
testcase_20 | AC | 332 ms
60,544 KB |
testcase_21 | AC | 578 ms
78,932 KB |
testcase_22 | AC | 348 ms
61,888 KB |
testcase_23 | AC | 590 ms
79,044 KB |
testcase_24 | AC | 277 ms
62,088 KB |
testcase_25 | AC | 548 ms
79,064 KB |
testcase_26 | AC | 189 ms
57,552 KB |
testcase_27 | AC | 487 ms
68,424 KB |
testcase_28 | AC | 486 ms
68,272 KB |
testcase_29 | AC | 365 ms
62,648 KB |
testcase_30 | AC | 587 ms
79,332 KB |
testcase_31 | AC | 213 ms
57,272 KB |
testcase_32 | AC | 207 ms
57,700 KB |
testcase_33 | AC | 636 ms
85,700 KB |
testcase_34 | AC | 664 ms
85,576 KB |
testcase_35 | AC | 636 ms
86,196 KB |
testcase_36 | AC | 633 ms
86,256 KB |
testcase_37 | AC | 643 ms
85,748 KB |
testcase_38 | AC | 642 ms
85,684 KB |
ソースコード
package no448a; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.InputMismatchException; import java.util.NoSuchElementException; import java.util.TreeSet; public class Main { public static long INF = 1L << 60; public static void main(String[] args) { // for(int i=0;i<1000;i++) { // test(); // } IO io = new IO(); int n = io.nextInt(); int k = io.nextInt(); long[] t = new long[n+1]; long[] d = new long[n+1]; for(int i=0;i<n;i++) { t[i] = io.nextLong(); d[i] = io.nextLong(); } t[n] = INF; for(long l: solve(n,k,t,d)) { System.out.println(l); } } public static long[] solve(int n,int k,long[] t,long[] d) { RangeMaximumQuery rmq = new RangeMaximumQuery(n+1); for(int i=0;i<=n;i++) { rmq.set(i, d[i]); } long[] dsum = new long[n+2]; for(int i=0;i<=n;i++) { dsum[i+1] = dsum[i] + d[i]; } int[] next = new int[n]; long[] rmqmax = new long[n]; for(int i=0;i<n;i++) { int idx = Arrays.binarySearch(t, t[i] + k); if (idx < 0) idx = ~idx; next[i] = idx; rmqmax[i] = rmq.max(i+1, idx); } TreeSet<Long> ts = new TreeSet<>(); for(int i=0;i<n;i++) { ts.add(d[i]); } ts.add(0L); ts.add(-1L); ArrayList<Long> ds = new ArrayList<>(ts); // System.out.println(ds); int left = 0; int right = ds.size()-1; while(left + 1 < right) { int c2 = (left + right) / 2; //大丈夫? long c = ds.get(c2); // System.out.println(c); long ans = method(n, k, t, d, rmqmax, dsum, c, next); if (ans < INF) { right = c2; }else{ left = c2; } } // System.out.println(right); return new long[] {ds.get(right) , method(n, k, t, d, rmqmax, dsum, ds.get(right), next)}; } public static int NMAX = 200000; public static long[] dp = new long[NMAX+1]; private static long method(int n, int k, long[] t, long[] d, long[] rmqmax, long[] dsum, long c, int[] next) { Arrays.fill(dp, INF); dp[0] = 0; for(int i=0;i<n;i++) { // System.out.println(dpmax[i] + "," + dpsum[i]); //やる if (d[i] <= c) { long sum = dp[i] + d[i]; // System.out.println((i+1) + ":" + max + "," + sum); if (sum < dp[i+1]) { dp[i+1] = sum; } } //投げる int idx = next[i]; long maxdiff = rmqmax[i]; if (maxdiff <= c) { long sum2 = dp[i]; if (i+1 <= idx) { sum2 += dsum[idx] - dsum[i+1]; } // System.out.println((idx) + ":" + max2 + "," + sum2); if (sum2 < dp[idx]) { dp[idx] = sum2; } } } return dp[n]; } } /* 0-indexed */ class BIT { private int n; private long[] bit; public BIT(int n) { this.n = n; bit = new long[n+1]; } public void accumulate(int index,long num) { index++; while(index<=n) { bit[index] += num; index+=index&-index; } } /* [begin , end) */ public long sum(int begin,int end) { return sum(end) - sum(begin); } private long sum(int i) { long s = 0; while(i>0) { s+=bit[i]; i-=i&-i; } return s; } public long get(int index) { return sum(index,index+1); } public void set(int index,long num) { accumulate(index,num-get(index)); } public String toString() { long[] value = new long[n]; for(int i=0;i<n;i++) { value[i] = get(i); } return Arrays.toString(value); } } class RangeMaximumQuery { public static final long INF = (1L<<60); private int size,n = 1; private long[] data; public RangeMaximumQuery(int size) { this.size = size; while(this.n<this.size) { this.n*=2; } data = new long[n*2-1]; this.init(); } private void init() { Arrays.fill(data, -INF); } public void set(int i,long x) { i+=n-1; data[i] = x; while(i>0) { i=(i-1)/2; data[i] = Math.max(data[i*2+1],data[i*2+2]); } } public long get(int i) { return data[i+n-1]; } public long max(long begin,long end) { return query(begin,end,0,0,n); } private long query(long a,long b,int k,int l,int r) { if (r<=a || b<=l) { return -INF; } if (a<=l && r<=b) { return data[k]; }else{ return Math.max(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r)); } } public String toString() { return Arrays.toString(Arrays.copyOfRange(data, n-1, size+n-1)); } } class IO extends PrintWriter { private final InputStream in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; public IO() { this(System.in);} public IO(InputStream source) { super(System.out); this.in = source;} private boolean hasNextByte() { if (ptr < buflen) { return true; }else{ ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;} private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;} private static boolean isNewLine(int c) { return c == '\n' || c == '\r';} public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();} public boolean hasNextLine() { while(hasNextByte() && isNewLine(buffer[ptr])) ptr++; return hasNextByte();} public String next() { if (!hasNext()) { throw new NoSuchElementException(); } StringBuilder sb = new StringBuilder(); int b = readByte(); while(isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public char[] nextCharArray(int len) { if (!hasNext()) { throw new NoSuchElementException(); } char[] s = new char[len]; int i = 0; int b = readByte(); while(isPrintableChar(b)) { if (i == len) { throw new InputMismatchException(); } s[i++] = (char) b; b = readByte(); } return s; } public String nextLine() { if (!hasNextLine()) { throw new NoSuchElementException(); } StringBuilder sb = new StringBuilder(); int b = readByte(); while(!isNewLine(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if (!hasNext()) { throw new NoSuchElementException(); } long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while(true){ if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; }else if(b == -1 || !isPrintableChar(b)){ return minus ? -n : n; }else{ throw new NumberFormatException(); } b = readByte(); } } public int nextInt() { long nl = nextLong(); if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) { throw new NumberFormatException(); } return (int) nl; } public char nextChar() { if (!hasNext()) { throw new NoSuchElementException(); } return (char) readByte(); } 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;} public long[] nextLongArray(int n) { long[] a = new long[n]; for(int i=0;i<n;i++) a[i] = nextLong(); return a;} public double[] nextDoubleArray(int n) { double[] a = new double[n]; for(int i=0;i<n;i++) a[i] = nextDouble(); return a;} public void nextIntArrays(int[]... a) { for(int i=0;i<a[0].length;i++) for(int j=0;j<a.length;j++) a[j][i] = nextInt();} public int[][] nextIntMatrix(int n,int m) { int[][] a = new int[n][]; for(int i=0;i<n;i++) a[i] = nextIntArray(m); return a;} public char[][] nextCharMap(int n,int m) { char[][] a = new char[n][]; for(int i=0;i<n;i++) a[i] = nextCharArray(m); return a;} public void close() { super.close(); try {in.close();} catch (IOException e) {}} }