Submission #523595

#	Time	Username	Problem	Language	Result	Execution time	Memory
523595		sverma2	Knapsack (NOI18_knapsack)	C++14	100 / 100	452 ms	18096 KiB

knapsack

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

using namespace std;

int dp[2001][2001]; // cost , weight class

bool cmp(pair<int, int> p1, pair<int, int> p2) {
  if(p1.first == p2.first) return p1.second > p2.second;
  else return p1.first > p2.first;
}

int main() {
	int S, N;
  cin >> S >> N;
  map<int, vector<pair<int, int> > > weight_class;
  for(int i = 0; i < N; i++) {
    int value, weight, frequency;
    cin >> value >> weight >> frequency;
    weight_class[weight].push_back(make_pair(value, frequency));
  }
  int ans = 0;
  int i = 1;
  for(auto cheese : weight_class) {
    int w = cheese.first;
    sort(weight_class[w].begin(), weight_class[w].end(), cmp);
    for(int cost = 1; cost <= S; cost++) {
      dp[cost][i] = dp[cost][i - 1];
      int amt_left = cost;
      int add = 0;
      int cnt = 0;
      for(auto goon : weight_class[w]) {
        int value = goon.first;
        int frequency = goon.second;
        // do around a 2000 iteration to compute the best dp[cost]
        int k = 0;
        while(cost - (cnt + 1) * w >= 0 && k < frequency) {
          add += value;
          dp[cost][i] = max(dp[cost][i], dp[cost - (cnt + 1) * w][i - 1] + add);
          // cout << cnt << "," << k << " " << "DP: " << cost << "," << i << ": " << dp[cost][i] << endl;
          ans = max(ans, dp[cost][i]);
          cnt++;
          k++;
        }
      }
    }
    i++;
  }
  cout << ans << endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:31:11: warning: unused variable 'amt_left' [-Wunused-variable]
   31 |       int amt_left = cost;
      |           ^~~~~~~~

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