結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー | bal4u |
提出日時 | 2019-04-25 09:42:14 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 1,977 bytes |
コンパイル時間 | 311 ms |
コンパイル使用メモリ | 31,232 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-17 18:47:59 |
合計ジャッジ時間 | 1,384 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
コンパイルメッセージ
main.c: In function 'in': main.c:8:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration] 8 | #define gc() getchar_unlocked() | ^~~~~~~~~~~~~~~~ main.c:16:34: note: in expansion of macro 'gc' 16 | long long n = 0; int c = gc(); | ^~
ソースコード
// yukicoder: No.545 ママの大事な二人の子供// 2019.4.25 bal4u#include <stdio.h>#include <stdlib.h>#if 1#define gc() getchar_unlocked()#define pc(c) putchar_unlocked(c)#else#define gc() getchar()#define pc(c) putchar(c)#endiflong long in() // 非負整数の入力{long long n = 0; int c = gc();do n = 10 * n + (c & 0xf), c = gc(); while (c >= '0');return n;}long long a[35], b[35]; int N;long long s[65600]; int sz;void precalc(long long *a, long long *b, long long *s, int n){int i, j;long long _s = 0;sz = 1 << n;for (i = 0; i < sz; i++) {_s = 0;for (j = 0; j < n; j++) {if ((i >> j) & 1) _s += a[j];else _s -= b[j];}s[i] = _s;}}int cmp(const void *a, const void *b){if (*(long long *)a < *(long long *)b) return -1;return *(long long *)a >= *(long long *)b;}int bsch(long long x){int m, l = 0, r = sz;while (l+1 < r) {m = (l+r) >> 1;if (s[m] < x) l = m; else r = m;}return r;}#define ABS(x) ((x)>=0?(x):-(x))int main(){int i, k, N, n, lim;long long ans;N = (int)in(), n = N/2;for (i = 0; i < N; i++) a[i] = in(), b[i] = in();if (n > 0) {precalc(a, b, s, n);qsort(s, sz, sizeof(long long), cmp);k = N - n, lim = 1 << k, ans = 0x7ffffffffffffffLL;for (i = 0; i < lim; i++) {long long t, d = 0;int m, j;for (j = 0; j < k; j++) {if ((i >> j) & 1) d += a[j+n];else d -= b[j+n];}m = bsch(-d);if (m >= 0 && m < sz) {t = ABS(s[m]+d);if (t == 0) { ans = 0; break; }if (t < ans) ans = t;}if (m > 0 && (t = ABS(s[m-1]+d)) < ans) ans = t;if (m+1 < sz && (t = ABS(s[m+1]+d)) < ans) ans = t;}} else {lim = 1 << N, ans = 0x7ffffffffffffffLL;for (i = 0; i < lim; i++) {long long t, d = 0;int j;for (j = 0; j < N; j++) {if ((i >> j) & 1) d += a[j+n];else d -= b[j+n];}if ((t = ABS(d)) < ans) ans = t;}}printf("%lld\n", ans);return 0;}