結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー | tanzaku |
提出日時 | 2017-07-14 22:49:40 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 312 ms / 2,000 ms |
コード長 | 1,493 bytes |
コンパイル時間 | 3,559 ms |
コンパイル使用メモリ | 78,436 KB |
実行使用メモリ | 55,944 KB |
最終ジャッジ日時 | 2024-10-07 23:43:27 |
合計ジャッジ時間 | 10,642 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
import java.util.*;public class No545 {public static void main(String[] args) {try (final Scanner sc = new Scanner(System.in)) {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();}if (n == 1) {System.out.println(Math.min(A[0], B[0]));return;}long[] s1 = new long[1<<(n/2)];long[] s2 = new long[1<<((n+1)/2)];for (int i = 0; i < 1<<(n/2); i++) {long s = 0;for (int j = 0; j < n/2; j++) {if ((i>>j&1) == 1) {s += A[j];} else {s -= B[j];}}s1[i] = s;}for (int i = 0; i < 1<<((n+1)/2); i++) {long s = 0;for (int j = 0; j < (n+1)/2; j++) {if ((i>>j&1) == 1) {s += A[n/2+j];} else {s -= B[n/2+j];}}s2[i] = s;}Arrays.sort(s1);Arrays.sort(s2);long ans = Long.MAX_VALUE;for (int i = 0, j = s2.length - 1; i < s1.length; i++) {for (; j > 0; j--) {long cur = Math.abs(s1[i] + s2[j]);long next = Math.abs(s1[i] + s2[j-1]);ans = Math.min(ans, cur);ans = Math.min(ans, next);if (cur < next) {break;}}}System.out.println(ans);}}static long gcd(long n, long r) { return r == 0 ? n : gcd(r, n % r); }static long lcm(long n, long r) { return n/gcd(n,r)*r; }static void dump(Object... objects) { System.err.println(Arrays.deepToString(objects)); }}