結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー |
![]() |
提出日時 | 2025-03-14 23:33:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 24 ms / 2,000 ms |
コード長 | 1,406 bytes |
コンパイル時間 | 2,036 ms |
コンパイル使用メモリ | 168,964 KB |
実行使用メモリ | 7,328 KB |
最終ジャッジ日時 | 2025-03-14 23:33:25 |
合計ジャッジ時間 | 3,410 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define endl '\n' typedef long long ll; const int N = 40; const ll inf = 0x3f3f3f3f3f3f3f3f; ll n; ll a[N], b[N]; int main(int argc, char const *argv[]) { // freopen("even.in", "r", stdin); // freopen("even.out", "w", stdout); ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); cin >> n; for (ll i = 1; i <= n; i++) cin >> a[i] >> b[i]; ll full = (1 << (n >> 1)); vector<ll> vec; for (ll S = 0; S < full; S++) { ll sum1 = 0, sum2 = 0; for (ll i = 0; i < (n >> 1); i++) { if ((S >> i) & 1) sum1 += a[i + 1]; else sum2 += b[i + 1]; } vec.push_back(sum1 - sum2); } sort(vec.begin(), vec.end()); ll ans = inf; for (ll S = 0; S < (1 << (n - (n >> 1))); S++) { ll sum1 = 0, sum2 = 0; for (ll i = 0; i < n - (n >> 1); i++) { if ((S >> i) & 1) sum1 += a[(n >> 1) + i + 1]; else sum2 += b[(n >> 1) + i + 1]; } ll tmp = sum1 - sum2; auto id = lower_bound(vec.begin(), vec.end(), -tmp); if (id != vec.end()) ans = min(ans, abs(tmp + *id)); if (id != vec.begin()) ans = min(ans, abs(tmp + *(id - 1))); } cout << ans << endl; return 0; }