Submission #919488

#	Time	Username	Problem	Language	Result	Execution time	Memory
919488		imann	Knapsack (NOI18_knapsack)	C++17	100 / 100	108 ms	22608 KiB

knapsack

#include <iostream>
#include <vector>
#include <cmath>
#include <map>
#include <algorithm>

typedef long long ll;

const int MAX_N = 1000*100 + 10;
const int MAX_S = 2*1000 + 10;
int Vs[MAX_N];
int Ws[MAX_N];
int Ks[MAX_N];
int dp[MAX_S][MAX_S];

struct Node {
  int w, k, v;
  bool operator > (const Node &n) const {
    return (v > n.v);
  }
};

int solve(std::vector<std::vector<Node> > &wvec, int s) {
  for (auto &v : wvec)
    std::sort(v.begin(), v.end(), std::greater<Node>());
  
  for (int i = 0; i < wvec.size(); ++i) {
    for (int j = 1; j <= s; ++j) {
      if (i > 0)
        dp[i][j] = dp[i - 1][j];
      int wc = 0, vc = 0;
      for (auto v : wvec[i]) {
        if (wc > j)
          break;
        for (int k = 1; k <= v.k; k++) {
          vc += v.v;
          wc += v.w;
          if (wc > j)
            break;
          if (i > 0)
            dp[i][j] = std::max(dp[i][j], dp[i - 1][j - wc] + vc);
          else
            dp[0][j] = vc;
        }
      }
    }
  }

  return dp[wvec.size() - 1][s];
}

int main() {
  int s, n; std::cin >> s >> n;
  for (int i = 0; i < n; ++i) {
    std::cin >> Vs[i] >> Ws[i] >> Ks[i];
  }
  std::map<int, std::vector<Node> > wmap;
  for (int i = 0; i < n; ++i)
    wmap[Ws[i]].push_back({Ws[i], Ks[i], Vs[i]});
  std::vector<std::vector<Node> > wvec;
  for (auto &v : wmap)
    wvec.push_back(v.second);
  std::cout << solve(wvec, s) << std::endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'int solve(std::vector<std::vector<Node> >&, int)':
knapsack.cpp:27:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<Node> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for (int i = 0; i < wvec.size(); ++i) {
      |                   ~~^~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27