fork download
copy 
  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4. typedef long long ll;
  5. #define INF 10000000000000000ll
  6.  
  7. const int exp3[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441};
  8. ll a[24], y[531441], bit[531442];
  9. int bit_size;
  10. inline void bit_init(int n){
  11.     bit_size = n;
  12.     for(int i=0; i<=bit_size; i++){
  13.         bit[i] = -INF;
  14.     }
  15. }
  16. inline ll bit_max(int i){
  17.     ll r = -INF;
  18.     for(; i; i-=i&-i){
  19.         r = max(r, bit[i]);
  20.     }
  21.     return r;
  22. }
  23. inline void bit_update(int i, ll x){
  24.     for(; i<=bit_size && bit[i]<x; i+=i&-i){
  25.         bit[i] = x;
  26.     }
  27. }
  28. struct jiken{
  29.     bool query;
  30.     ll x, y;
  31.     jiken(bool q=false, ll x=0, ll y=0): query(q), x(x), y(y){}
  32.     bool operator <(const jiken &b) const{
  33.         if(x == b.x){
  34.             return !query && b.query;
  35.         }
  36.         return x < b.x;
  37.     }
  38. }sl[1062882];
  39.  
  40. int main(){
  41.     int n;
  42.     scanf("%d", &n);
  43.     for(int i=0; i<=n-1; i++) scanf("%lld", a+i);
  44.     ll s = 0;
  45.     for(int i=0; i<=n-1; i++) s += a[i];
  46.     int m=0, ysz=0;
  47.     for(int i=0; i<exp3[n/2]; i++){
  48.         ll p=0, q=0;
  49.         for(int j=0, t=i; j<=n/2; j++, t/=3){
  50.             if(t%3 == 1){
  51.                 p += a[j];
  52.             }else if(t%3 == 2){
  53.                 q += a[j];
  54.             }
  55.         }
  56.         sl[m++] = jiken(false, p-q, p+2*q);
  57.         y[ysz++] = p+2*q;
  58.     }
  59.     sort(y, y+ysz);
  60.     ysz = unique(y, y+ysz)-y;
  61.     for(int i=0; i<exp3[(n+1)/2]; i++){
  62.         ll p=0, q=0;
  63.         for(int j=0, t=i; j<=(n+1)/2-1; j++, t/=3){
  64.             if(t%3 == 1){
  65.                 p += a[n/2+j];
  66.             }else if(t%3 == 2){
  67.                 q += a[n/2+j];
  68.             }
  69.         }
  70.         sl[m++] = jiken(true, -p+q, s-p-2*q);
  71.     }
  72.     sort(sl, sl+m);
  73.     ll ans = INF;
  74.     bit_init(ysz);
  75.     for(int i=0; i<=m-1; i++){
  76.         int j = upper_bound(y, y+ysz, sl[i].y)-y;
  77.         if(sl[i].query){
  78.             ans = min(ans, sl[i].x+sl[i].y-bit_max(j));
  79.         }else{
  80.             bit_update(j, sl[i].x+sl[i].y);
  81.         }
  82.     }
  83.     printf("%lld\n", ans);
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 0.01s 27412KB
comments (?)
stdin
copy 
4
5 4 7 6
stdout
copy 
3
https://ideone.com/7u8TS2
language:
C++14 (gcc 8.3)
created:
6 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!