Submission #2090549

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
void rd(long long &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
void wt_L(long long x){
  char f[20];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
template<class S, class T> inline S chmin(S &a, T b){
  if(a>b){
    a=b;
  }
  return a;
}
template<class S, class T> inline S chmax(S &a, T b){
  if(a<b){
    a=b;
  }
  return a;
}
int N, bt[300000];
long long C[20], V[20], X[20], dp[300000], dp2[20][300000], sumC[300000], sumV[300000], sumX[20];
long long solve(int mask, int cnt){
  int i;
  long long res=0, tmp;
  if(dp[mask] >= 0){
    return dp[mask];
  }
  res = dp2[cnt][mask];
  if(mask){
    tmp = 4611686016279904256LL;
    for(i=0;i<N;i++){
      if(mask&1<<i){
        chmin(tmp, solve(mask^(1<<i), cnt+1));
      }
    }
    chmax(res, tmp);
  }
  return dp[mask] = res;
}
int main(){
  int i, j, k;
  long long res;
  rd(N);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=0;Lj4PdHRW<N;Lj4PdHRW++){
      rd(X[Lj4PdHRW]);
    }
  }
  {
    int KL2GvlyY;
    for(KL2GvlyY=0;KL2GvlyY<N;KL2GvlyY++){
      rd(C[KL2GvlyY]);
    }
  }
  {
    int Q5VJL1cS;
    for(Q5VJL1cS=0;Q5VJL1cS<N;Q5VJL1cS++){
      rd(V[Q5VJL1cS]);
    }
  }
  for(i=0;i<N;i++){
    bt[1<<i] = i;
  }
  for(i=1;i<1<<N;i++){
    j = i&(-i);
    sumC[i] = sumC[i^j] + C[bt[j]];
    sumV[i] = sumV[i^j] + V[bt[j]];
  }
  sumX[0] = 0;
  for(i=0;i<N;i++){
    sumX[i+1] = sumX[i] + X[i];
  }
  for(k=0;k<N+1;k++){
    for(i=0;i<1<<N;i++){
      if(sumC[i] <= sumX[k]){
        dp2[k][i] = sumV[i];
        continue;
      }
      dp2[k][i] = 0;
      for(j=0;j<N;j++){
        if(i&1<<j){
          chmax(dp2[k][i], dp2[k][i^(1<<j)]);
        }
      }
    }
  }
  for(i=0;i<1<<N;i++){
    dp[i] = -1;
  }
  res = solve((1<<N)-1, 0);
  wt_L(res);
  putchar_unlocked('\n');
  return 0;
}
// cLay varsion 20180208-1

// --- original code ---
// int N;
// ll X[20], C[20], V[20];
// 
// ll dp[3d5];
// 
// ll sumX[20];
// ll sumC[3d5], sumV[3d5];
// ll dp2[20][3d5];
// int bt[3d5];
// 
// ll solve(int mask, int cnt){
//   int i;
//   ll res = 0, tmp;
// 
//   if(dp[mask] >= 0) return dp[mask];
// 
//   res = dp2[cnt][mask];
// 
//   if(mask){
//     tmp = ll_inf;
//     rep(i,N) if(mask&1<<i){
//       tmp <?= solve(mask^(1<<i), cnt+1);
//     }
//     res >?= tmp;
//   }
// 
//   return dp[mask] = res;
// }
// 
// {
//   int i, j, k;
//   ll res;
// 
//   rd(N,X(N),C(N),V(N));
// 
//   rep(i,N) bt[1<<i] = i;
//   rep(i,1,1<<N){
//     j = i&(-i);
//     sumC[i] = sumC[i^j] + C[bt[j]];
//     sumV[i] = sumV[i^j] + V[bt[j]];
//   }
//   
//   sumX[0] = 0;
//   rep(i,N) sumX[i+1] = sumX[i] + X[i];
//   
//   rep(k,N+1){
//     rep(i,1<<N){
//       if(sumC[i] <= sumX[k]){
//         dp2[k][i] = sumV[i];
//         continue;
//       }
//       dp2[k][i] = 0;
//       rep(j,N) if(i&1<<j){
//         dp2[k][i] >?= dp2[k][i^(1<<j)];
//       }
//     }
//   }
//   
//   rep(i,1<<N) dp[i] = -1;
//   res = solve((1<<N)-1, 0);
// 
//   wt(res);
// }

Submission Info

Judge Result