結果
問題 | No.1008 Bench Craftsman |
ユーザー | 37zigen |
提出日時 | 2020-04-01 03:59:13 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,127 ms / 2,000 ms |
コード長 | 1,597 bytes |
コンパイル時間 | 2,869 ms |
コンパイル使用メモリ | 75,436 KB |
実行使用メモリ | 73,840 KB |
最終ジャッジ日時 | 2023-09-08 03:08:04 |
合計ジャッジ時間 | 25,127 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 122 ms
55,736 KB |
testcase_01 | AC | 122 ms
55,564 KB |
testcase_02 | AC | 120 ms
55,556 KB |
testcase_03 | AC | 123 ms
56,624 KB |
testcase_04 | AC | 124 ms
56,012 KB |
testcase_05 | AC | 1,127 ms
69,284 KB |
testcase_06 | AC | 648 ms
62,124 KB |
testcase_07 | AC | 118 ms
55,368 KB |
testcase_08 | AC | 266 ms
60,504 KB |
testcase_09 | AC | 662 ms
67,328 KB |
testcase_10 | AC | 992 ms
69,544 KB |
testcase_11 | AC | 990 ms
67,108 KB |
testcase_12 | AC | 980 ms
67,352 KB |
testcase_13 | AC | 992 ms
67,364 KB |
testcase_14 | AC | 857 ms
65,660 KB |
testcase_15 | AC | 828 ms
67,128 KB |
testcase_16 | AC | 995 ms
66,932 KB |
testcase_17 | AC | 842 ms
65,240 KB |
testcase_18 | AC | 955 ms
67,156 KB |
testcase_19 | AC | 903 ms
65,264 KB |
testcase_20 | AC | 629 ms
63,844 KB |
testcase_21 | AC | 657 ms
62,328 KB |
testcase_22 | AC | 764 ms
70,924 KB |
testcase_23 | AC | 888 ms
71,564 KB |
testcase_24 | AC | 903 ms
69,760 KB |
testcase_25 | AC | 663 ms
62,084 KB |
testcase_26 | AC | 592 ms
61,888 KB |
testcase_27 | AC | 766 ms
65,704 KB |
testcase_28 | AC | 819 ms
67,648 KB |
testcase_29 | AC | 976 ms
73,840 KB |
ソースコード
import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; class Main { public static void main(String[] args) { new Main().run(); } boolean f(long[] A,int[] x,long[] w,long c) { int N=A.length,M=x.length; boolean ret=true; if(c==0) { long sum=Arrays.stream(w).sum(); return sum<Arrays.stream(A).min().getAsLong(); } long[] v=new long[N+1]; int[] L=new int[M]; int[] R=new int[M]; for(int i=0;i<M;++i) { //w-|i-x|c=0 ⇔ i=x±w/c //(-\infty,floor(x-w/c)], [ceil(x+w/c),\infty] L[i]=Math.max(-1,(int)(x[i]-(w[i]+c-1)/c)); R[i]=Math.min(+N,(int)(x[i]+(w[i]+c-1)/c)); v[L[i]+1]+=c; v[x[i]+1]-=2*c; v[R[i]]+=c; } for(int i=1;i<=N;++i) { v[i]+=v[i-1]; } for(int i=0;i<M;++i) {// w-|q-x|*c v[L[i]+1]+=(w[i]-Math.abs(L[i]+1-x[i])*c)-c; v[R[i]]-=(w[i]-Math.abs(R[i]-1-x[i])*c); } for(int i=1;i<=N;++i) { v[i]+=v[i-1]; } for(int i=0;i<N;++i)ret&=v[i]<A[i]; return ret; } void run() { Scanner sc=new Scanner(System.in); int N=sc.nextInt(); int M=sc.nextInt(); long[] A=new long[N]; for(int i=0;i<N;++i)A[i]=Long.parseLong(sc.next()); int[] x=new int[M]; long[] w=new long[M]; for(int i=0;i<M;++i) { x[i]=Integer.parseInt(sc.next())-1; w[i]=Long.parseLong(sc.next()); } long INF=(long)1e6; long ok=INF; long ng=-1; while(ok-ng>1) { long middle=(ok+ng)/2; if(f(A,x,w,middle)) { ok=middle; }else { ng=middle; } } System.out.println(ok==INF?-1:ok); } static void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }