結果
問題 | No.1008 Bench Craftsman |
ユーザー | 37zigen |
提出日時 | 2020-04-01 03:55:17 |
言語 | Java21 (openjdk 21) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,628 bytes |
コンパイル時間 | 2,395 ms |
コンパイル使用メモリ | 76,248 KB |
実行使用メモリ | 76,548 KB |
最終ジャッジ日時 | 2023-09-08 03:01:09 |
合計ジャッジ時間 | 24,840 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 127 ms
55,564 KB |
testcase_01 | AC | 128 ms
55,920 KB |
testcase_02 | AC | 122 ms
55,816 KB |
testcase_03 | AC | 128 ms
56,176 KB |
testcase_04 | AC | 127 ms
55,920 KB |
testcase_05 | AC | 1,133 ms
72,232 KB |
testcase_06 | AC | 682 ms
64,056 KB |
testcase_07 | AC | 125 ms
55,800 KB |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | AC | 1,041 ms
67,548 KB |
testcase_11 | AC | 1,040 ms
74,684 KB |
testcase_12 | AC | 976 ms
65,392 KB |
testcase_13 | AC | 995 ms
65,984 KB |
testcase_14 | AC | 1,018 ms
67,452 KB |
testcase_15 | AC | 844 ms
65,568 KB |
testcase_16 | AC | 957 ms
66,072 KB |
testcase_17 | AC | 979 ms
69,720 KB |
testcase_18 | AC | 870 ms
63,536 KB |
testcase_19 | AC | 950 ms
65,700 KB |
testcase_20 | AC | 690 ms
64,624 KB |
testcase_21 | AC | 665 ms
61,772 KB |
testcase_22 | RE | - |
testcase_23 | RE | - |
testcase_24 | RE | - |
testcase_25 | AC | 684 ms
65,976 KB |
testcase_26 | AC | 554 ms
64,352 KB |
testcase_27 | RE | - |
testcase_28 | AC | 815 ms
67,828 KB |
testcase_29 | AC | 974 ms
76,548 KB |
ソースコード
import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; class Main { public static void main(String[] args) { new Main().run(); } final long MOD=(long)1e9+7; 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[N]; int[] R=new int[N]; 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)); } }