fork(1) download 
  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. int n, bit_size;
  9. ll a[24], y[4096], bit[4097];
  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-y == b.x-b.y){
  34.             return !query && b.query;
  35.         }
  36.         return x-y < b.x-b.y;
  37.     }
  38. }sl[1062882];
  39.  
  40. ll loli(){
  41.     int m=0, ysz=0;
  42.     ll s = 0;
  43.     for(int i=0; i<=n-1; i++) s += a[i];
  44.     for(int i=0; i<exp3[n/2]; i++){
  45.         ll p=0, q=0;
  46.         for(int j=0, t=i; j<=n/2; j++, t/=3){
  47.             if(t%3 == 1){
  48.                 p += 3*a[j];
  49.             }else if(t%3 == 2){
  50.                 q += 3*a[j];
  51.             }
  52.         }
  53.         sl[m++] = jiken(false, p, q);
  54.     }
  55.     for(int i=0; i<(1<<n/2); i++){
  56.         ll t = 0;
  57.         for(int j=0; j<=n/2-1; j++){
  58.             t += 3*(i>>j&1)*a[j];
  59.         }
  60.         y[ysz++] = t;
  61.     }
  62.     sort(y, y+ysz);
  63.     ysz = unique(y, y+ysz)-y;
  64.     for(int i=0; i<exp3[(n+1)/2]; i++){
  65.         ll p=0, q=0;
  66.         for(int j=0, t=i; j<=(n+1)/2-1; j++, t/=3){
  67.             if(t%3 == 1){
  68.                 p += 3*a[n/2+j];
  69.             }else if(t%3 == 2){
  70.                 q += 3*a[n/2+j];
  71.             }
  72.         }
  73.         sl[m++] = jiken(true, s-p, s-q);
  74.     }
  75.     sort(sl, sl+m);
  76.     ll ans = INF;
  77.     bit_init(ysz);
  78.     for(int i=0; i<=m-1; i++){
  79.         int j = upper_bound(y, y+ysz, sl[i].y)-y;
  80.         if(sl[i].query){
  81.             ans = min(ans, 2*sl[i].x+sl[i].y-bit_max(j));
  82.         }else{
  83.             bit_update(j, 2*sl[i].x+sl[i].y);
  84.         }
  85.     }
  86.     return ans/3;
  87. }
  88.  
  89. int main(){
  90.     scanf("%d", &n);
  91.     for(int i=0; i<=n-1; i++) scanf("%lld", a+i);
  92.     ll ans = loli();
  93.     for(int i=0; i<=n-1; i++) a[i] = -a[i];
  94.     ans = min(ans, loli());
  95.     printf("%lld\n", ans);
  96.     return 0;
  97. }
  98.  
Success #stdin #stdout 0.01s 27564KB
comments (?)
stdin 
4
5 4 7 6
stdout 
3
https://ideone.com/CMTdMh
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!