Submission #1109842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109842		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	86 ms	3656 KiB

knapsack

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

typedef pair<int, int> PI;

int main() {
  int N, S;
  cin >> S >> N;
  vector<vector<pair<int, int>>> items;
  items.resize(S + 1);
  for (int i = 0, v, w, k; i < N; ++i) {
    cin >> v >> w >> k;
    items[w].push_back({v, k});
  }
  for (int i = 1; i <= S; ++i) {
    sort(items[i].begin(), items[i].end(), [](const PI& a, const PI& b) {
      return a.first > b.first;
    });
  }

  long long dp[2][3001];
  memset(dp, 0, sizeof(dp));
  for (int s = 1; s <= S; ++s) {
    // easy access for items
    vector<int> vals;
    for (int i = 0; i < items[s].size(); ++i) {
      for (int j = 0; vals.size() * s <= S && j < items[s][i].second; ++j) {
        vals.push_back(items[s][i].first);
      }
    }

    long long (&a)[3001] = dp[s&1];
    long long (&b)[3001] = dp[(s-1)&1];
    for (int i = 0; i <= S; ++i) {
      a[i] = b[i];
      long long tv = 0;
      for (int j = 0, tw = s; tw <= i && j < vals.size(); ++j, tw+=s) {
        tv += vals[j];
        long long tmp = b[i - tw] + tv;
        a[i] = max(tmp, a[i]);
      }
    }
  }

  long long ans = 0;
  for (int i = 0; i <= S; ++i) {
    ans = max(ans, dp[S&1][i]);
  }
  cout << ans << endl;
  
  return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0; i < items[s].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~
knapsack.cpp:30:39: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |       for (int j = 0; vals.size() * s <= S && j < items[s][i].second; ++j) {
      |                       ~~~~~~~~~~~~~~~~^~~~
knapsack.cpp:40:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |       for (int j = 0, tw = s; tw <= i && j < vals.size(); ++j, tw+=s) {
      |                                          ~~^~~~~~~~~~~~~

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