Submission #1253759

---

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 wt_L(int x){
  char f[10];
  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 void chmax(S &a, T b){
  if(a<b){
    a=b;
  }
}
int H[100], N, V[100], W, gain[4][100], sum[4][101], sz[4];
int main(){
  int a, b, c, d, res=0;
  long long minH, r;
  rd(N);
  rd(W);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=0;Lj4PdHRW<N;Lj4PdHRW++){
      rd(H[Lj4PdHRW]);
      rd(V[Lj4PdHRW]);
    }
  }
  minH = H[0];
  {
    int KL2GvlyY;
    for(KL2GvlyY= 0;KL2GvlyY< (N-1) + 1;KL2GvlyY++){
      H[KL2GvlyY] -= minH;
    }
  }
  {
    int Q5VJL1cS;
    for(Q5VJL1cS= 0;Q5VJL1cS< (N-1) + 1;Q5VJL1cS++){
      gain[H[Q5VJL1cS]][sz[H[Q5VJL1cS]]++] = V[Q5VJL1cS];
    }
  }
  {
    int e98WHCEY;
    for(e98WHCEY= 0;e98WHCEY< (3) + 1;e98WHCEY++){
      sort(gain[e98WHCEY], gain[e98WHCEY]+sz[e98WHCEY], greater<int>());
    }
  }
  {
    int cTE1_r3A;
    for(cTE1_r3A= 0;cTE1_r3A< (3) + 1;cTE1_r3A++){
      {
        int RZTsC2BF;
        for(RZTsC2BF= 1;RZTsC2BF< (sz[cTE1_r3A]) + 1;RZTsC2BF++){
          sum[cTE1_r3A][RZTsC2BF] += sum[cTE1_r3A][RZTsC2BF - (1) + (0)] + gain[cTE1_r3A][RZTsC2BF - (1) + (0)];
        }
      }
    }
  }
  for(a=0;a<sz[0]+1;a++){
    for(b=0;b<sz[1]+1;b++){
      for(c=0;c<sz[2]+1;c++){
        r = W - minH*a - (minH+1)*b - (minH+2)*c;
        if(r < 0){
          break;
        }
        d = min(r / (minH+3), (long long)sz[3]);
        chmax(res, sum[0][a] + sum[1][b] + sum[2][c] + sum[3][d]);
      }
    }
  }
  wt_L(res);
  putchar_unlocked('\n');
  return 0;
}
// cLay varsion 20170429-1

// --- original code ---
// int N, W, H[100], V[100];
// int gain[4][100], sum[4][101], sz[4];
// {
//   int res = 0;
//   int a, b, c, d;
//   ll r, minH;
//   rd(N, W, (H,V)(N));
//   minH = H[0];
//   H[0..N-1] -= minH;
//   gain[H[0..N-1]][sz[H[0..]]++] = V[0..];
//   sort(gain[0..3], gain[0..]+sz[0..], greater<int>());
// 
//   sum[0...3][1..sz[0...]] += sum[0...][0..] + gain[0...][0..];
// 
//   rep(a,sz[0]+1) rep(b,sz[1]+1) rep(c,sz[2]+1){
//     r = W - minH*a - (minH+1)*b - (minH+2)*c;
//     if(r < 0) break;
//     d = min(r / (minH+3), (ll)sz[3]);
//     res >?= sum[0][a] + sum[1][b] + sum[2][c] + sum[3][d];
//   }
//   wt(res);
// }

Submission Info

Judge Result