結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー |
|
提出日時 | 2017-11-04 18:01:28 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 1,161 bytes |
コンパイル時間 | 1,934 ms |
コンパイル使用メモリ | 168,164 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-23 18:02:38 |
合計ジャッジ時間 | 2,676 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define REP(i,n) FOR(i,0,n) #define FOR(i,a,b) for(ll i=a;i<b;i++) #define PB push_back #define LB lower_bound #define UB upper_bound #define PQ priority_queue #define UM unordered_map #define ALL(a) (a).begin(),(a).end() #define MOD 1000000007 typedef vector<ll> vi; typedef vector<vector<ll>> vvi; const ll INF = (1ll << 30); typedef pair<ll,ll> pii; struct Edge{ ll s,t,c; }; typedef vector<vector<ll>> Graph; typedef vector<pii> vpii; vi f(vpii v) { ll n=v.size(); vi ret; REP(i,(1ll<<n)) { ll sum=0; REP(j,n) if((1ll<<j)&i) sum+=v[j].first; else sum-=v[j].second; ret.PB(sum); } sort(ALL(ret)); return ret; } int main() { ll n; cin>>n; vpii v(n); REP(i,n) cin>>v[i].first>>v[i].second; if(n==1) { cout<<min(v[0].first,v[0].second)<<endl; return 0; } vpii v1,v2; REP(i,n/2) v1.PB(v[i]); FOR(i,n/2,n) v2.PB(v[i]); vi a1=f(v1),a2=f(v2); ll ans=INF; for(ll i:a1) { auto it=lower_bound(ALL(a2),-i); if(it!=a2.end()) ans=min(ans,abs(*it+i)); if(it!=a2.begin()) ans=min(ans,abs(*prev(it)+i)); } cout<<ans<<endl; }