Submission #774787

#	Time	Username	Problem	Language	Result	Execution time	Memory
774787		scrge	Knapsack (NOI18_knapsack)	C++17	0 / 100	4 ms	6356 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
const int S = 2000;

int s, n;
multiset<int, greater<int>> vals[S];

signed main(){
  cin >> s >> n;
  for(int i = 0; i < n; i++){
    int v, w, k;
    cin >> v >> w >> k;
    while(k-- && 
      ((vals[w].size() == (s/w)+1 && v > *vals[w].lower_bound(v)) 
      || vals[w].size() < s)){
      if(vals[w].size() == s)
        vals[w].erase(prev(vals[w].end()));
      vals[w].insert(v);
    }
  }

  /*
  for(int i = 0; i < s; i++){
    cout << i << ": ";
    for(int j: vals[i]) cout << j << " ";
    cout << endl;
  }*/

  int dp[s+5][s+5];
  memset(dp, 0, sizeof dp);
  for(int i = 1; i <= s; i++){
    int cur_w = 0, cur_v = 0;
    for(int j = 0; j <= s; j++)
      dp[i+1][j] = dp[i][j];
    for(int v: vals[i]){
      cur_w += i, cur_v += v; 
      if(cur_w >= s) break;
      for(int j = cur_w; j <= s; j++){
        dp[i+1][j-cur_w] = max(dp[i+1][j-cur_w], dp[i][j]+cur_v);
      }
    }
  }
  int ans = 0;
  for(int i = 0; i <= s; i++)
    ans = max(ans, dp[s+1][i]);
  cout << ans << endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:14:24: warning: comparison of integer expressions of different signedness: 'std::multiset<int, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   14 |       ((vals[w].size() == (s/w)+1 && v > *vals[w].lower_bound(v))
      |         ~~~~~~~~~~~~~~~^~~~~~~~~~
knapsack.cpp:15:25: warning: comparison of integer expressions of different signedness: 'std::multiset<int, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |       || vals[w].size() < s)){
      |          ~~~~~~~~~~~~~~~^~~
knapsack.cpp:16:25: warning: comparison of integer expressions of different signedness: 'std::multiset<int, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   16 |       if(vals[w].size() == s)
      |          ~~~~~~~~~~~~~~~^~~~

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