結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー |
![]() |
提出日時 | 2019-02-24 16:54:46 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 21 ms / 2,000 ms |
コード長 | 1,795 bytes |
コンパイル時間 | 821 ms |
コンパイル使用メモリ | 76,672 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-23 06:29:19 |
合計ジャッジ時間 | 1,913 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include <iostream> #include <algorithm> #include <cstring> #include <sstream> #include <map> #include <queue> #include <set> #include <vector> #include <stack> #include <cstdio> #include <cmath> #define mk make_pair #define pb push_back #define printf printf_s #define scanf scanf_s using namespace std; typedef long long int ll; typedef pair<ll, ll> pos; const ll MOD = 1000000007, N = 300010, dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 }, MIN = -72340172838076673, MAX = 72340172838076673; ll mn(ll a, ll b) { if (a == -1)return b; if (b == -1)return a; return min(a, b); } ll gcd(ll v1, ll v2) { if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2); } ll pw(ll v1, ll v2) { ll v3 = 1; while (v2 > 0) { if (v2 % 2)v3 = (v3*v1) % MOD; v1 = (v1*v1) % MOD; v2 /= 2; } return v3; } struct ab { ll a, b; bool operator<(const ab& right) const { return right.b*a - right.a*b < 0; } }; ll n, d1[1 << 16], d2[1 << 16], l1, l2; pos ab[32]; int main() { cin >> n; for (int i = 0; i < n; i++)cin >> ab[i].first >> ab[i].second; ll md = n / 2; l1 = (1 << md); l2 = (1 << (n - md)); for (int s = 0; s < (1 << md); s++) { ll v1 = 0; for (int i = 0; i < md; i++) { if ((s >> i) & 1)v1 += ab[i].first; else v1 -= ab[i].second; } d1[s] = v1; } for (int s = 0; s < (1<<(n - md)); s++) { ll v1 = 0; for (int i = 0; i < n - md; i++) { if ((s >> i) & 1)v1 += ab[md + i].first; else v1 -= ab[md + i].second; } d2[s] = v1; } sort(d1, d1 + l1); sort(d2, d2 + l2); ll ans = -1; for (int i = 0; i < l1; i++) { ll i1 = lower_bound(d2, d2 + l2, -d1[i]) - d2; if (i1 != l2)ans = mn(ans, abs(d1[i] + d2[i1])); if (i1 - 1 >= 0)ans = mn(ans, abs(d1[i] + d2[i1 - 1])); } cout << ans << endl; return 0; }