結果
問題 | 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<<60void _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;}