結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー | uafr_cs |
提出日時 | 2017-10-30 21:37:54 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 508 ms / 2,000 ms |
コード長 | 2,083 bytes |
コンパイル時間 | 2,352 ms |
コンパイル使用メモリ | 81,232 KB |
実行使用メモリ | 56,336 KB |
最終ジャッジ日時 | 2024-11-22 10:56:50 |
合計ジャッジ時間 | 11,191 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.HashMap;import java.util.LinkedList;import java.util.Scanner;import java.util.TreeSet;public class Main {public static ArrayList<Long> all(int begin, int end, long[] as, long[] bs){TreeSet<Long> set = new TreeSet<Long>();final int size = end - begin;final int bit_size = 1 << size;for(int bit = 0; bit < bit_size; bit++){long sum = 0;for(int i = 0; i < size; i++){final int index = i + begin;if((bit & (1 << i)) == 0){sum += as[index];}else{sum -= bs[index];}}set.add(sum);}return new ArrayList<Long>(set);}public static void main(String[] args) {Scanner sc = new Scanner(System.in);final int n = sc.nextInt();long[] as = new long[n];long[] bs = new long[n];for(int i = 0; i < n; i++){as[i] = sc.nextLong();bs[i] = sc.nextLong();}if(n == 1){System.out.println(Math.min(as[0], bs[0]));return;}final int fst_end = n / 2;ArrayList<Long> fst_part = all(0, fst_end, as, bs);ArrayList<Long> snd_part = all(fst_end, n, as, bs);//System.out.println(fst_part);//System.out.println(snd_part);long answer = Long.MAX_VALUE;for(int fst_index = 0; fst_index < fst_part.size(); fst_index++){final long snd = - fst_part.get(fst_index);final int snd_index = Collections.binarySearch(snd_part, snd);if(snd_index >= 0){System.out.println(0);return;}else{final int lower = -(snd_index + 2);if(lower >= 0){//System.out.println(fst_part.get(fst_index) + " " + snd_part.get(lower));answer = Math.min(answer, Math.abs(snd_part.get(lower)+ fst_part.get(fst_index)));}final int upper = -(snd_index + 1);if(upper < snd_part.size()){//System.out.println(fst_part.get(fst_index) + " " + snd_part.get(upper));answer = Math.min(answer, Math.abs(snd_part.get(upper) + fst_part.get(fst_index)));}}}System.out.println(answer);}}