結果
問題 | No.1925 悪鬼三七次元 |
ユーザー | 37zigen |
提出日時 | 2022-04-26 22:27:15 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 637 ms / 2,000 ms |
コード長 | 2,356 bytes |
コンパイル時間 | 2,256 ms |
コンパイル使用メモリ | 76,696 KB |
実行使用メモリ | 63,240 KB |
最終ジャッジ日時 | 2023-09-13 22:28:15 |
合計ジャッジ時間 | 30,913 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 637 ms
60,888 KB |
testcase_01 | AC | 625 ms
60,656 KB |
testcase_02 | AC | 631 ms
61,636 KB |
testcase_03 | AC | 586 ms
61,032 KB |
testcase_04 | AC | 590 ms
61,208 KB |
testcase_05 | AC | 578 ms
60,812 KB |
testcase_06 | AC | 613 ms
60,904 KB |
testcase_07 | AC | 615 ms
60,732 KB |
testcase_08 | AC | 621 ms
61,016 KB |
testcase_09 | AC | 620 ms
61,044 KB |
testcase_10 | AC | 593 ms
60,800 KB |
testcase_11 | AC | 588 ms
60,616 KB |
testcase_12 | AC | 610 ms
60,892 KB |
testcase_13 | AC | 590 ms
61,096 KB |
testcase_14 | AC | 625 ms
60,892 KB |
testcase_15 | AC | 623 ms
60,656 KB |
testcase_16 | AC | 590 ms
61,004 KB |
testcase_17 | AC | 585 ms
60,924 KB |
testcase_18 | AC | 613 ms
60,744 KB |
testcase_19 | AC | 585 ms
60,980 KB |
testcase_20 | AC | 619 ms
60,916 KB |
testcase_21 | AC | 589 ms
61,068 KB |
testcase_22 | AC | 616 ms
60,852 KB |
testcase_23 | AC | 557 ms
61,192 KB |
testcase_24 | AC | 519 ms
60,240 KB |
testcase_25 | AC | 376 ms
60,812 KB |
testcase_26 | AC | 271 ms
60,504 KB |
testcase_27 | AC | 417 ms
60,372 KB |
testcase_28 | AC | 478 ms
60,328 KB |
testcase_29 | AC | 415 ms
60,924 KB |
testcase_30 | AC | 539 ms
60,956 KB |
testcase_31 | AC | 492 ms
60,452 KB |
testcase_32 | AC | 356 ms
63,240 KB |
testcase_33 | AC | 400 ms
60,456 KB |
testcase_34 | AC | 499 ms
61,040 KB |
testcase_35 | AC | 481 ms
60,340 KB |
testcase_36 | AC | 371 ms
60,596 KB |
testcase_37 | AC | 459 ms
60,484 KB |
testcase_38 | AC | 455 ms
58,784 KB |
testcase_39 | AC | 558 ms
60,588 KB |
testcase_40 | AC | 546 ms
60,748 KB |
testcase_41 | AC | 500 ms
60,980 KB |
testcase_42 | AC | 510 ms
60,384 KB |
ソースコード
import java.io.PrintWriter; import java.util.Arrays; import java.util.Random; import java.util.Scanner; public class Main implements Runnable { //Runnableを実装する public static void main(String[] args) { // new Thread(null, new Main(), "", 16 * 1024 * 1024).start(); //16MBスタックを確保して実行 new Main().run(); } final long INF=Long.MAX_VALUE/3; long f(long[] a, boolean maximize) { if (a.length==1) return a[0]; long ret=maximize?-INF:INF; for (int i=0;i<=a.length;++i) { long[] na=new long[a.length]; for (int j=0;j<i;++j) na[j]+=a[j]; for (int j=i+1;j<a.length;++j) na[j-1]+=a[j]; if (i!=0&&i!=a.length) na[i-1]+=a[i]; na=Arrays.copyOf(na, a.length-1); if (maximize) ret=Math.max(ret, f(na, !maximize)); else ret=Math.min(ret, f(na, !maximize)); } return ret; } long solve_even(long[] a) { int len=a.length/2+1; long sum=Arrays.stream(Arrays.copyOf(a, len)).sum(); long ans=sum; for (int i=len;i<a.length;++i) { sum+=-a[i-len]+a[i]; ans=Math.min(ans, sum); } return ans; } long solve_odd(long[] a) { int n=a.length; long ok=1; long ng=Long.MAX_VALUE/3; while (ng-ok>1) { long m=(ok+ng)/2; int cnt=0; for (int i=0;i<a.length;++i) { int j=i; long s=a[i]; while (j+1<a.length && s<m) { s+=a[j+1]; j+=1; } if (s >= m) ++cnt; i=j; } if (cnt>=(n+1)/2) ok=m; else ng=m; } return ok; } long solve(long[] a) { return a.length%2==0?solve_even(a):solve_odd(a); } public void run() { Scanner sc=new Scanner(System.in); PrintWriter pw=new PrintWriter(System.out); // Random rnd=new Random(); // while (true) { // int N=rnd.nextInt(1,10); // long[] a=new long[N]; // for (int i=0;i<a.length;++i) a[i]=rnd.nextInt(1, 10); // long solve1=f(a, true); // long solve2=solve(a); // if (solve1==solve2) tr("ok"); // else { // tr(a); // tr(solve1, solve2); // return; // } // } int N=sc.nextInt(); long[] A=new long[N]; for (int i=0;i<N;++i) A[i]=sc.nextInt(); System.out.println(solve(A)); pw.close(); } void tr(Object ... o) {System.out.println(Arrays.deepToString(o));} }