結果
問題 |
No.545 ママの大事な二人の子供
|
ユーザー |
|
提出日時 | 2023-05-20 10:28:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,753 bytes |
コンパイル時間 | 788 ms |
コンパイル使用メモリ | 78,056 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-21 08:57:46 |
合計ジャッジ時間 | 3,813 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 WA * 2 RE * 11 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; void halr_sum(vector<long long int> a,vector<long long int> b,long long int temp_sum,int i,int end, vector<long long int> &sum){ if(i==end){ sum.push_back(temp_sum); return; } halr_sum(a,b,temp_sum+a[i],i+1,end,sum); halr_sum(a,b,temp_sum-b[i],i+1,end,sum); } int main(){ int n; cin >> n; vector<long long int> a(n),b(n); for(int i=0; i<n; i++){ cin >> a[i]>>b[i]; } // Sum_i in Select (a[i]) とSum_i in Not Select (b[i])の // 差の絶対値の最小値を求める // 1<=n<=32 // 0<=a[i],b[i]<=5*10^9 // 単純に計算すると2^32=2^10*3 *4 =4* 10^9 なので間に合わない. // なお,2^16 = 64*1000=6*10^4である. // 従って,グループを2グループに分け,それぞれで全通りで差を計算する.(半分全列挙) // この時,差について各 -\inf ~ 0 | \inf がある. // 従って,各上,下から確かめれば良い. int lc=n/2,rc=n-lc; vector<long long int> l(lc),r(rc); vector<long long int> lsum,rsum;// それぞれありうる合計値の差異のリスト. halr_sum(a,b,0,0,lc,lsum); halr_sum(a,b,0,lc,n,rsum); sort(lsum.begin(),lsum.end()); sort(rsum.begin(),rsum.end()); long long int ans=5*(long long int)1000000000*32;// lsum,rsumの合計の絶対値最小になる時の値を探す. // method1 int rnum=rsum.size()-1; int j = 0; while(j < lsum.size() || rnum > 0){ if(llabs(lsum[j] + rsum[rnum]) > llabs(lsum[j] + rsum[rnum - 1])){ rnum--; }else{ ans = min(ans,llabs(lsum[j] + rsum[rnum])); j++; } } ans = min(ans,llabs(lsum[j] + rsum[rnum])); // int j=rsum.size()-1; // long long int temp=ans; // for(int i=0;i<lsum.size();i++){ // temp=lsum[i]+rsum[j]; // ans=min(ans,abs(temp)); // while(temp>0 && j>0){ // j--; // temp=lsum[i]+rsum[j];// jを下げていくとtempは減少する. // ans=min(ans,abs(temp)); // } // } // method 2 /* long long int k; for(int i=0;i<lsum.size();i++){ // lsum[i]の相方を見つける k = lower_bound(rsum.begin(), rsum.end(), -lsum[i]) - rsum.begin(); temp=lsum[i]+rsum[j]; ans=min(ans,abs(temp)); if(0 <= k && k < rsum.size()) ans = min(ans, abs(lsum[i]+rsum[k])); if(0 <= k-1 && k-1 < rsum.size()) ans = min(ans, abs(lsum[i]+rsum[k-1])); if(0 <= k+1 && k+1 < rsum.size()) ans = min(ans, abs(lsum[i]+rsum[k+1])); } */ cout << ans << endl; return 0; }