Submission #923747

#	Time	Username	Problem	Language	Result	Execution time	Memory
923747		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	69 ms	37452 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int const N = 2002;
vector<pair<ll, int>> I[N];
vector<ll> W[N];
ll dp[N][N];

int S, n;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> S >> n;
    for (int i = 0; i < n; ++i) {
        ll v; int w, k; cin >> v >> w >> k;
        I[w].emplace_back(-v, k);
    }
    for (int i = 1; i < N; ++i) {
        sort(I[i].begin(), I[i].end());
        W[i].push_back(0);
        for (auto& [v, k]: I[i]) {
            for (int j = 0; j < k; ++j) {
                W[i].push_back(W[i].back() - v);
                if (W[i].size() * i - i > S) break; 
            }
        }
        I[i].clear();
    }
    for (int w = 1; w <= S; ++w) {
        for (int s = S; s >= 0; --s) {
            for (int c = 0; c < W[w].size() && c*w <= s; ++c) {
                dp[w][s] = max(dp[w][s], W[w][c] + dp[w-1][s - c*w]);
            }
        }
    }
    cout << dp[S][S] << '\n';
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:25:41: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |                 if (W[i].size() * i - i > S) break;
      |                     ~~~~~~~~~~~~~~~~~~~~^~~
knapsack.cpp:32:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             for (int c = 0; c < W[w].size() && c*w <= s; ++c) {
      |                             ~~^~~~~~~~~~~~~

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