結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー |
![]() |
提出日時 | 2017-07-15 15:36:29 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 879 bytes |
コンパイル時間 | 1,633 ms |
コンパイル使用メモリ | 165,928 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-08 02:26:59 |
合計ジャッジ時間 | 2,900 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long int64; int main() { int64 N, A[32], B[32]; cin >> N; for(int i = 0; i < N; i++) cin >> A[i] >> B[i]; int mid = N / 2; vector< int64 > st; for(int i = 0; i < 1 << mid; i++) { int64 beet = 0; for(int j = 0; j < mid; j++) { if((i >> j) & 1) beet += A[j]; else beet -= B[j]; } st.push_back(beet); } sort(begin(st), end(st)); st.erase(unique(begin(st), end(st)), end(st)); int64 ret = 1LL << 58; for(int i = 0; i < 1 << (N - mid); i++) { int64 beet = 0; for(int j = mid; j < N; j++) { if((i >> (j - mid)) & 1) beet += A[j]; else beet -= B[j]; } auto p = lower_bound(begin(st), end(st), -beet); if(end(st) != p) ret = min(ret, llabs(*p + beet)); if(begin(st) != p) ret = min(ret, llabs(*--p + beet)); } cout << ret << endl; }