Submission #620188

#	Time	Username	Problem	Language	Result	Execution time	Memory
620188		ThinGarfield	Knapsack (NOI18_knapsack)	C++11	100 / 100	135 ms	3784 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define mp make_pair
#define F first
#define S second

constexpr int maxn = 100005;
constexpr int maxs = 2005;

int n, s;

vector<pii> items_list[maxs];  // items[w] = [all pairs (v, k) with value w]
vector<pii> items;             // items = list of (value,weight), sorted, at most s/w items per w

int knapsack() {
  int N = items.size();
  int K[2][maxs];

  for (int i = 0; i <= N; i++) {
    for (int w = 0; w <= s; w++) {
      if (i == 0 || w == 0)
        K[i % 2][w] = 0;
      else if (items[i - 1].S <= w)
        K[i % 2][w] = max(items[i - 1].F + K[(i - 1) % 2][w - items[i - 1].S], K[(i - 1) % 2][w]);
      else
        K[i % 2][w] = K[(i - 1) % 2][w];
    }
  }
  return K[N % 2][s];
}

int main() {
  // ios_base::sync_with_stdio(false);
  // cin.tie(NULL);

  cin >> s >> n;
  for (int i = 0; i < n; i++) {
    int v, w, k;
    cin >> v >> w >> k;
    items_list[w].pb(mp(v, k));
  }
  for (int i = 1; i <= s; i++) {
    // sort by value
    sort(items_list[i].begin(), items_list[i].end(), greater<pii>());

    // add items to items
    int counter = 0;
    for (pii item_type : items_list[i]) {
      for (int j = 0; j < item_type.S; j++) {
        if (counter == s / i) break;
        items.push_back(mp(item_type.F, i));
        counter++;
      }
    }
  }

  // for (pii item : items) {
  //   cout << "value: " << item.F << '\t' << "weight: " << item.S << '\n';
  // }

  cout << knapsack() << '\n';

  return 0;
}

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