Submission #1304744

---

Source Code Expand

#include <cstdio>
#include <vector>
 
struct state {
  int aw;
  int av;
  state(int aw=0, int av=0): aw(aw), av(av) {}
};
 
int n, w, c;
 
 
std::vector<state> is[50];
 
std::vector<state> tmp;
 
std::vector<state> dp[51][2];

int maxv;
double maxr;
 
void merge(const std::vector<state> &s, const std::vector<state> &t, std::vector<state> &u){
  auto i = s.cbegin();
  auto j = t.cbegin();
  for(; i != s.cend() && j != t.cend();){
    if(i->aw <= j->aw && i->av >= j->av) ++j;
    else if(i->aw >= j->aw && i->av <= j->av) ++i;
    else if(i->aw < j->aw) u.push_back(*i++);
    else u.push_back(*j++);
  }
  while(i != s.cend()) u.push_back(*i++);
  while(j != t.cend()) u.push_back(*j++);
}
 
void mergei(const std::vector<state> &s, const state &k, std::vector<state> &u){
  auto i = s.cbegin();
  auto j = s.cbegin();
  for(; i != s.cend() && j != s.cend() && j->aw + k.aw <= w;){
    if(i->aw <= j->aw + k.aw && i->av >= j->av + k.av) ++j;
    else if(i->aw >= j->aw + k.aw && i->av <= j->av + k.av) ++i;
    else if(i->aw < j->aw + k.aw) u.push_back(*i++);
    else {u.emplace_back(state(j->aw + k.aw, j->av + k.av)); ++j;}
  }
  while(i != s.cend()) u.push_back(*i++);
  while(j != s.cend() && j->aw + k.aw <= w){
    u.emplace_back(state(j->aw + k.aw, j->av + k.av));
    ++j;
  }
}
 
void shrink(const std::vector<state> &s, std::vector<state> &t){
//  printf("B %d\n", s.size());
  for(auto x: s){
    if(x.av + (w-x.aw)*maxr + 0.5 >= maxv) t.push_back(x);
//    if(1) t.push_back(x);
  }
//  printf("A %d\n", t.size());
}
 
 
int main(){
  scanf("%d%d%d", &n, &w, &c);
  for(int i=0;i<n;i++){
    int ww, vv, cc;
    scanf("%d%d%d",&ww,&vv,&cc);
    if(ww <= w){
      is[cc-1].emplace_back(state(ww, vv));
      maxr = std::max(maxr, (double) vv / ww);
    }
  }
 
  tmp.reserve(500);

  for(int i=0;i<=50;i++){
    dp[i][0].reserve(500);
    dp[i][1].reserve(500);
    dp[i][0].emplace_back(state(0, 0));
    dp[i][1].emplace_back(state(0, 0));
  }
 
  for(int i=0;i<50;i++){
    if(is[i].empty()) continue;
    for(int k = 1; k <= c; k++){
      merge(dp[k][1], dp[k][0], tmp);
      dp[k][0].resize(0);
      shrink(tmp, dp[k][0]);
      tmp.resize(0);
      dp[k][1].resize(0);
      mergei(dp[k-1][0], is[i][0], dp[k][1]);
      maxv = std::max(maxv, dp[k][1].back().av);
    }
    for(auto j = is[i].cbegin()+1; j != is[i].cend(); ++j){
      for(int k = 1; k <= c; k++){
        mergei(dp[k][1], *j, tmp);
        maxv = std::max(maxv, tmp.back().av);
        dp[k][1].resize(0);
        shrink(tmp, dp[k][1]);
        tmp.resize(0);
      }
    }
  }
 
  printf("%d\n", maxv);
 
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:62:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &n, &w, &c);
                              ^
./Main.cpp:65:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&ww,&vv,&cc);
                                ^

Judge Result