結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー | mban |
提出日時 | 2017-07-15 00:14:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 24 ms / 2,000 ms |
コード長 | 1,691 bytes |
コンパイル時間 | 1,191 ms |
コンパイル使用メモリ | 102,524 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-08 00:18:51 |
合計ジャッジ時間 | 2,459 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include <algorithm>#include <cmath>#include <complex>#include <cstdlib>#include <functional>#include <iomanip>#include <iostream>#include <limits.h>#include <map>#include <math.h>#include <numeric>#include <queue>#include <stdio.h>#include <stdlib.h>#include <string>#include <time.h>#include <vector>using namespace std;#define ll long longint N;std::vector<ll> A, B;std::vector<ll> a, b;void dfsa(ll aa, ll bb, int n) {if (N / 2 == n) {a.push_back(aa - bb);return;}dfsa(aa + A[n], bb, n + 1);dfsa(aa, bb + B[n], n + 1);}void dfsb(ll aa, ll bb, int n) {if (N == n) {b.push_back(aa - bb);return;}dfsb(aa + A[n], bb, n + 1);dfsb(aa, bb + B[n], n + 1);}int main() {cin >> N;A = std::vector<ll>(N);B = std::vector<ll>(N);for (int i = 0; i < N; i++) {cin >> A[i] >> B[i];}dfsa(0, 0, 0);dfsb(0, 0, N / 2);sort(b.begin(), b.end());ll ans = LLONG_MAX;for (ll i : a) {int left = 0;int right = b.size();while (right - left > 1) {int mid = (left + right) / 2;if (i + b[mid] <= 0) {left = mid;} else {right = mid;}}ans = min(ans, abs(i + b[left]));left = -1;right = b.size() - 1;while (right - left > 1) {int mid = (left + right) / 2;if (i + b[mid] >= 0) {right = mid;} else {left = mid;}}ans = min(ans, abs(i + b[right]));}cout << ans << endl;return 0;}