結果
問題 | No.595 登山 |
ユーザー | 夕叢霧香(ゆうむらきりか) |
提出日時 | 2017-11-10 23:17:30 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 901 ms / 1,500 ms |
コード長 | 1,821 bytes |
コンパイル時間 | 2,369 ms |
コンパイル使用メモリ | 74,436 KB |
実行使用メモリ | 79,432 KB |
最終ジャッジ日時 | 2023-08-16 05:15:35 |
合計ジャッジ時間 | 20,012 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 116 ms
62,204 KB |
testcase_01 | AC | 114 ms
62,228 KB |
testcase_02 | AC | 113 ms
60,448 KB |
testcase_03 | AC | 109 ms
62,476 KB |
testcase_04 | AC | 752 ms
79,432 KB |
testcase_05 | AC | 383 ms
69,992 KB |
testcase_06 | AC | 709 ms
79,088 KB |
testcase_07 | AC | 266 ms
66,780 KB |
testcase_08 | AC | 312 ms
69,128 KB |
testcase_09 | AC | 722 ms
79,324 KB |
testcase_10 | AC | 505 ms
72,224 KB |
testcase_11 | AC | 479 ms
71,536 KB |
testcase_12 | AC | 257 ms
67,180 KB |
testcase_13 | AC | 371 ms
69,452 KB |
testcase_14 | AC | 633 ms
74,380 KB |
testcase_15 | AC | 718 ms
77,976 KB |
testcase_16 | AC | 727 ms
78,376 KB |
testcase_17 | AC | 740 ms
77,876 KB |
testcase_18 | AC | 735 ms
77,912 KB |
testcase_19 | AC | 882 ms
77,988 KB |
testcase_20 | AC | 901 ms
78,208 KB |
testcase_21 | AC | 879 ms
78,176 KB |
testcase_22 | AC | 811 ms
78,520 KB |
testcase_23 | AC | 887 ms
78,772 KB |
testcase_24 | AC | 119 ms
62,096 KB |
testcase_25 | AC | 115 ms
61,908 KB |
testcase_26 | AC | 890 ms
78,444 KB |
testcase_27 | AC | 758 ms
78,016 KB |
testcase_28 | AC | 762 ms
78,092 KB |
ソースコード
import java.util.*; class Main { static final long I=1L<<50; public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n=Integer.parseInt(scan.next()); long p=Integer.parseInt(scan.next()); long[] h=new long[n]; for(int i=0;i<n;++i) h[i]=Integer.parseInt(scan.next()); long[] l=new long[n],r=new long[n]; l[0]=r[n-1]=0; for(int i=1;i<n;++i) l[i]=l[i-1]+Math.max(h[i]-h[i-1],0); for(int i=n-2;i>=0;--i) r[i]=r[i+1]+Math.max(h[i]-h[i+1],0); MaxSegmentTree s1=new MaxSegmentTree(); MaxSegmentTree s2=new MaxSegmentTree(); long[] dp=new long[n]; dp[0]=0; dp[1]=0; s1.update(0,l[1]); s2.update(0,-r[1]); for(int i=1;i<n;++i){ long m=l[i]; m=Math.min(m,-s1.query(0,i)+l[i]+p); m=Math.min(m,-s2.query(0,i)-r[i]+p); dp[i]=m; if(i<n-1){ s1.update(i,-m+l[i+1]); s2.update(i,-m-r[i+1]); } } System.out.println(dp[n-1]); } } class MaxSegmentTree { static final int SIZE = 1 << 18; static final long INFINITY = (1L << 61) - 1; long[] seg; MaxSegmentTree() { this.seg = new long[2 * SIZE]; } void update(int x, long value) { x += SIZE - 1; this.seg[x] = value; while (x > 0) { x = (x - 1) / 2; this.seg[x] = Math.max(this.seg[2 * x + 1], this.seg[2 * x + 2]); } } long query(int l, int r) { l += SIZE - 1; r += SIZE - 1; long y = -INFINITY; while (l < r) { if ((l & 1) == 0) { y = Math.max(y, this.seg[l]); } if ((r & 1) == 0) { y = Math.max(y, this.seg[r - 1]); } l /= 2; r = (r - 1) / 2; } return y; } }