結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー | はまやんはまやん |
提出日時 | 2017-07-14 22:35:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 24 ms / 2,000 ms |
コード長 | 2,181 bytes |
コンパイル時間 | 1,905 ms |
コンパイル使用メモリ | 177,400 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-07 23:39:55 |
合計ジャッジ時間 | 3,267 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<b;i++) #define fore(i,a) for(auto &i:a) #pragma GCC optimize ("-O3") using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } //--------------------------------------------------------------------------------------------------- /*--------------------------------------------------------------------------------------------------- ∧_∧ ∧_∧ (´<_` ) Welcome to My Coding Space! ( ´_ゝ`) / ⌒i / \ | | / / ̄ ̄ ̄ ̄/ | __(__ニつ/ _/ .| .|____ \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ typedef long long ll; int N; ll A[40], B[40]; //--------------------------------------------------------------------------------------------------- vector<ll> solve(vector<int> &a) { vector<ll> res; int n = a.size(); rep(mask, 0, 1 << n) { ll d = 0; rep(i, 0, n) { if (mask & (1 << i)) d += A[a[i]]; else d -= B[a[i]]; } res.push_back(d); } sort(res.begin(), res.end()); res.erase(unique(res.begin(), res.end()), res.end()); return res; } //--------------------------------------------------------------------------------------------------- #define INF 1LL<<60 void _main() { cin >> N; rep(i, 0, N) cin >> A[i] >> B[i]; vector<int> a, b; rep(i, 0, N) { if (i % 2 == 0) a.push_back(i); else b.push_back(i); } auto aa = solve(a); auto bb = solve(b); ll ans = INF; fore(i, aa) { int j = lower_bound(bb.begin(), bb.end(), -i) - bb.begin(); ll mi = INF; if (0 <= j && j < bb.size()) mi = min(mi, abs(i + bb[j])); if (0 <= j - 1 && j - 1 < bb.size()) mi = min(mi, abs(i + bb[j - 1])); if (0 <= j + 1 && j + 1 < bb.size()) mi = min(mi, abs(i + bb[j + 1])); ans = min(ans, mi); } cout << ans << endl; }