結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー | Shun_PI |
提出日時 | 2017-07-15 12:53:26 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 220 ms / 2,000 ms |
コード長 | 3,575 bytes |
コンパイル時間 | 2,335 ms |
コンパイル使用メモリ | 77,916 KB |
実行使用メモリ | 41,364 KB |
最終ジャッジ日時 | 2024-10-08 02:20:48 |
合計ジャッジ時間 | 6,577 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
import java.io.IOException;import java.io.InputStream;import java.util.Arrays;import java.util.NoSuchElementException;public class Main {private static FastScanner sc = new FastScanner();public static void main(String[] args) {int n = sc.nextInt();long[] A = new long[n];long[] B = new long[n];for(int i=0; i<n; i++) {A[i] = sc.nextLong();B[i] = -sc.nextLong();}int ln = n / 2;int rn = n - ln;long[] left = new long[1<<ln];for(int i=0; i<(1<<ln); i++) {for(int j=0; j<ln; j++) {if((i>>j & 1) == 1) {left[i] += A[j];} else {left[i] += B[j];}}// System.out.println(left[i]);}long[] right = new long[1<<rn];for(int i=0; i<(1<<rn); i++) {for(int j=0; j<rn; j++) {if((i>>j & 1) == 1) {right[i] += A[ln + j];} else {right[i] += B[ln + j];}}}Arrays.sort(right);// for(int i=0; i<(1<<rn); i++) {// System.out.println(right[i]);// }long ans = Long.MAX_VALUE;for(int i=0; i<(1<<ln); i++) {int l = 0;int r = (1<<rn) - 1;int m = (l + r) / 2;while(l < r) {// System.out.println("i=" + i + " l=" + l + " r=" + r);m = (l + r) / 2;if(left[i] + right[m] < 0) {if(m == 1<<rn - 1) {break;} else if(Math.abs(left[i] + right[m]) < Math.abs(left[i] + right[m+1])) {break;} else {l = m+1;}} else {if(m == 0) {break;} else if(Math.abs(left[i] + right[m]) < Math.abs(left[i] + right[m-1])) {break;} else {r = m-1;}}}if(Math.abs(left[i] + right[m]) < ans) {ans = Math.abs(left[i] + right[m]);}if(m+1 < 1<<rn && Math.abs(left[i] + right[m+1]) < ans) {ans = Math.abs(left[i] + right[m+1]);}if(m-1 >= 0 && Math.abs(left[i] + right[m-1]) < ans) {ans = Math.abs(left[i] + right[m-1]);}}System.out.println(ans);}static class FastScanner {private final InputStream in = System.in;private final byte[] buffer = new byte[1024];private int ptr = 0;private int buflen = 0;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 void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}public boolean hasNext() { skipUnprintable(); 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 long nextLong() {return Long.parseLong(next());}public int nextInt(){return Integer.parseInt(next());}public double nextDouble(){return Double.parseDouble(next());}}}