結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー | kkty |
提出日時 | 2017-11-04 18:01:28 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 1,161 bytes |
コンパイル時間 | 1,496 ms |
コンパイル使用メモリ | 168,300 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-05-02 22:46:45 |
合計ジャッジ時間 | 2,792 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 3 ms
5,376 KB |
testcase_20 | AC | 4 ms
5,376 KB |
testcase_21 | AC | 1 ms
5,376 KB |
testcase_22 | AC | 14 ms
5,376 KB |
testcase_23 | AC | 25 ms
5,376 KB |
testcase_24 | AC | 11 ms
5,376 KB |
testcase_25 | AC | 23 ms
5,376 KB |
testcase_26 | AC | 24 ms
5,376 KB |
testcase_27 | AC | 22 ms
5,376 KB |
testcase_28 | AC | 25 ms
5,376 KB |
testcase_29 | AC | 22 ms
5,376 KB |
testcase_30 | AC | 23 ms
5,376 KB |
testcase_31 | AC | 23 ms
5,376 KB |
ソースコード
#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; }