結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー | erbowl |
提出日時 | 2018-06-14 22:40:51 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 143 ms / 2,000 ms |
コード長 | 1,851 bytes |
コンパイル時間 | 1,456 ms |
コンパイル使用メモリ | 161,876 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-30 14:32:51 |
合計ジャッジ時間 | 3,695 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
typedef long long ll;#include <bits/stdc++.h>using namespace std;int main() {ll n,a[32],b[32];cin >>n;for (int i = 0; i < n; i++) {cin >>a[i]>>b[i];}ll A_B[65536];for (int i = 0; i < (ll)pow(2,n/2); i++) {// std::cout << i << std::endl;ll rem=i;ll A=0;ll B=0;ll j=n/2-1;while(j>=0){if(rem/(ll)pow(2,j)>0){rem-=(ll)pow(2,j);A+=a[j];}else{B+=b[j];}j--;}A_B[i]=A-B;// std::cout << A-B<<" ";}// std::cout << std::endl;sort(A_B,A_B+(ll)pow(2,n/2));ll A_B_2[65536];for (int i = 0; i < (ll)pow(2,n-n/2); i++) {// std::cout << i << std::endl;ll rem=i;ll A=0;ll B=0;ll j=n-n/2-1;while(j>=0){if(rem/(ll)pow(2,j)>0){rem-=(ll)pow(2,j);A+=a[j+n/2];}else{B+=b[j+n/2];}j--;}A_B_2[i]=A-B;// std::cout << A-B<<" ";}// std::cout << std::endl;sort(A_B_2,A_B_2+(ll)pow(2,n-n/2));// for (int i = 0; i < (ll)pow(2,n/2); i++) {// std::cout << A_B[i]<<" ";// }// std::cout << std::endl;// for (int i = 0; i < (ll)pow(2,n-n/2); i++) {// std::cout << A_B_2[i]<<" ";// }// std::cout << std::endl;ll res=5000000000;for (int i = 0; i < (ll)pow(2,n/2); i++) {ll aa=distance(A_B_2,lower_bound(A_B_2, A_B_2+(ll)pow(2,n-n/2) , -A_B[i]));// std::cout << aa << std::endl;res=min(res,abs(A_B[i]+A_B_2[aa]));if(aa>0){res=min(res,abs(A_B[i]+A_B_2[aa-1]));}}std::cout << res << std::endl;}