Submission #673378

#	Time	Username	Problem	Language	Result	Execution time	Memory
673378		MADE_IN_HEAVEN	Knapsack (NOI18_knapsack)	C++17	100 / 100	207 ms	39192 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define what(a) cout << (#a) << " is " << (a) << '\n';

int s , n;
const int N = 2002;
long long memo[N][N];
bool visited[N][N];
vector<pair<int , int>>by_weight[N];

long long dp(int weight , int remain) {

  if(remain < 0) return -1e18;
  if(weight >= N) return 0;

  if(visited[weight][remain]) return memo[weight][remain];

  long long res = -1e18;
  res = max(res , dp(weight + 1 , remain));

  int copies = 0 , kur = 0 , take_from_kur = 0;
  long long advantage = 0;

  while((copies + 1) * weight <= remain && kur < by_weight[weight].size()) {
    advantage += by_weight[weight][kur].first;
    copies++;
    ++take_from_kur;

    if(take_from_kur >= by_weight[weight][kur].second) kur++ , take_from_kur = 0;

    res = max(res , advantage + dp(weight + 1 , remain - (copies * weight)));
  }

  memo[weight][remain] = res;
  visited[weight][remain] = true;
  return res;
}

void solve() {

  cin >> s >> n;

  for(int i = 0 ; i < n ; i++) {
    int value , weight , copies;
    cin >> value >> weight >> copies;
    by_weight[weight].push_back(make_pair(value , copies));
  }

  for(int i = 0 ; i < N ; i++) {
    sort(by_weight[i].rbegin() , by_weight[i].rend());
    //what(i);
    //for(auto [j , k] : by_weight[i]) cout << j << ' ' << k << '\n';
  }

  cout << dp(1 , s);
  return;
}

int main() {

  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int tt = 1;
  // cin >> tt;
  while(tt--) {
    solve();
  }

  return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'long long int dp(int, int)':
knapsack.cpp:24:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   while((copies + 1) * weight <= remain && kur < by_weight[weight].size()) {
      |                                            ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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