fork download
copy 
  1. #include<bits/stdc++.h>
  2. // GCC 優化程式碼：關閉一些檢查讓時間
  3. #pragma GCC optimize("Ofast")
  4. #pragma GCC target("sse3", "sse2", "sse")
  5. #pragma GCC target("avx", "sse4", "sse4.1", "sse4.2", "ssse3")
  6. #pragma GCC target("f16c")
  7. #pragma GCC optimize("inline", "fast-math", "unroll-loops", "no-stack-protector")
  8. #pragma GCC diagnostic error "-fwhole-program"
  9. #pragma GCC diagnostic error "-fcse-skip-blocks"
  10. #pragma GCC diagnostic error "-funsafe-loop-optimizations"
  11. #pragma GCC diagnostic error "-std=c++14"
  12. using namespace std;
  13.  
  14. string ss;
  15. const int MAXN=10005;
  16. int target, num_sum, num_cnt, now_x;
  17. int num[MAXN];
  18. vector<int> pos[2];
  19.  
  20. void DFS(int,int,int,int);// 產生所有可能的數字
  21. int main(){
  22.   ios::sync_with_stdio(0),
  23.   cin.tie(0), cout.tie(0);
  24.  
  25.   while(getline(cin,ss)){
  26.     int p=0;
  27.     for(now_x=num_cnt=0; ss[p]!=0; p++)
  28.       (ss[p]<'0')? num[num_cnt++]=now_x,now_x=0: now_x=10*now_x+ss[p]-'0';
  29.  
  30.     num[num_cnt++]=now_x;
  31.     num_sum=0;
  32.     for(int i=0;i<num_cnt;i++)
  33.       num_sum+=num[i];
  34.     target=num_sum>>1;
  35.     /* =====分情況討論=====
  36.      * (1)根據 num_cnt 小於等於42個決定是否可以採用暴力法
  37.      * (2)作弊...反例：9999個31時
  38.      */
  39.     if(num_cnt<=42){ // 枚舉暴力法的極限<- 卡在第二筆測資的上限
  40.       // 雙向BFS
  41.       now_x=num_cnt>>1;
  42.       pos[0].clear();
  43.       pos[1].clear();
  44.       DFS(    0,  now_x,0,0);
  45.       DFS(now_x,num_cnt,1,0);
  46.       sort(pos[0].begin(),pos[0].end());
  47.       sort(pos[1].begin(),pos[1].end());
  48.       int near_target=0;
  49.       for(int x:pos[0])
  50.         if(x<=target)
  51.           now_x=upper_bound(pos[1].begin(),pos[1].end(),target-x)-pos[1].begin(),
  52.           near_target=max(near_target,x+pos[1][now_x-1]);
  53.         else
  54.           break;
  55.       cout<<(long)near_target*(num_sum-near_target)<<'\n';
  56.     }else // 無法用暴力法時就直接輸出總和的一半視為最佳解
  57.       cout<<(long)target*(num_sum-target)<<'\n';
  58.   }
  59. }
  60. void DFS(int st,int ed,int sz,int v){
  61.   pos[sz].push_back(v);
  62.   for(int i=st;i<ed;i++)
  63.     DFS(i+1,ed,sz,v+num[i]);
  64. }
Success #stdin #stdout 0s 15400KB
comments (?)
stdin
copy 
6 1 7 3 5 2 6 4 1 3
7 3 4 1 6 1 2 5 2 1 7 6 3 2 4 1 2 1 3 1
7 3 5 4 1 6 8 4 3 2 2 1 6 4 6 4 2 1 3 4 6 5 2 4 1
stdout
copy 
361
961
2209
https://ideone.com/GnKv1U
ZJ-b952( DFS+CutBranch )
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!