結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー | myanta |
提出日時 | 2017-07-14 23:43:15 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 66 ms / 2,000 ms |
コード長 | 1,229 bytes |
コンパイル時間 | 653 ms |
コンパイル使用メモリ | 54,212 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2024-10-07 23:53:42 |
合計ジャッジ時間 | 2,191 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:65:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 65 | scanf("%lld%lld", &a[i], &b[i]); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include<cstdio>#include<vector>#include<set>#include<cstdlib>#include<algorithm>using namespace std;using ll=long long;using vll=vector<ll>;void min_u(ll&m, ll v){if(m<0 || m>v){m=v;}}ll search(vll& u, ll ve){int s=0, e=u.size()-1, c, r=0;while(s<=e){c=(s+e)/2;ll d=u[c]+ve;//printf("s=%d e=%d c=%d d=%lld ve=%lld\n", s, e, c, d, ve);if(d==0) return 0;if(d>0){e=c-1;r=c-1;}else{s=c+1;r=c;}}if(r<0) r=0;ll ret=llabs(u[r]+ve);if(r+1<u.size()) min_u(ret, llabs(u[r+1]+ve));return ret;}int main(void){int n;while(scanf("%d", &n)==1){vll a(n), b(n);set<ll> u, v;vll s;for(int i=0;i<n;i++){scanf("%lld%lld", &a[i], &b[i]);}u.insert(0);for(int i=0;i<n/2;i++){auto t=u;u.clear();for(auto te:t){u.insert(te+a[i]);u.insert(te-b[i]);}}v.insert(0);for(int i=n/2;i<n;i++){auto t=v;v.clear();for(auto te:t){v.insert(te+a[i]);v.insert(te-b[i]);}}s.reserve(v.size());for(auto ve:v){s.push_back(ve);}ll ans=-1;for(auto ue:u){min_u(ans, search(s, ue));}printf("%lld\n", ans);}return 0;}