Submission #1304727

---

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];
 
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;
  }
}
 
 
 
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);
    is[cc-1].emplace_back(state(ww, vv));
  }
 

  for(int i=0;i<=50;i++){
    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].swap(tmp);
      tmp.resize(0);
      dp[k][1].resize(0);
      mergei(dp[k-1][0], is[i][0], dp[k][1]);
    }
    for(auto j = is[i].cbegin()+1; j != is[i].cend(); ++j){
//      for(int k = 1; k <= c; k++){
      for(int k = std::max(1, c-(50-i)); k <= c; k++){
        mergei(dp[k][1], *j, tmp);
        dp[k][1].swap(tmp);
        tmp.resize(0);
      }
    }
  }
 
  printf("%d\n", std::max(dp[c][0].back().av, dp[c][1].back().av));
 
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:51: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:54: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