Submission #993540

#	Time	Username	Problem	Language	Result	Execution time	Memory
993540		niwrad	Knapsack (NOI18_knapsack)	C++17	100 / 100	97 ms	19536 KiB

knapsack

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <array>
#include <cstdio>
#include <vector>
#include <string>
#include <fstream>
#include <tuple>
#include <numeric>
#include <map>
#include <iomanip>
#include <math.h>
#include <queue>
#include <sstream>
#include <stack>
#include <initializer_list>
#include <functional>
#include <cstring>
#include <unordered_map>



using namespace std;
long long mod = 1e9 + 7;

struct item {
    int v, w, k;
};

int main() {
    //freopen("longpath.in", "r", stdin);
    //freopen("longpath.out", "w", stdout);
    int n, s;
    cin >> s >> n;
    vector<item> vec(n);
    for (int i = 0; i < n; i++) {
        cin >> vec[i].v >> vec[i].w >> vec[i].k;
    }
    vector<vector<int>> value(2001);
    sort( vec.begin( ), vec.end( ), [ ]( const item& x, const item& y )
    {
        if (x.w == y.w) {
            return x.v > y.v;
        }
        return x.w < y.w;
    });
    for (int i = 0; i < n; i++) {
        if (value[vec[i].w].size() < s / vec[i].w) {
            int si = s / vec[i].w - (int) value[vec[i].w].size();
            for (int j = 0; j < min(vec[i].k, si); j++) {
                value[vec[i].w].push_back(vec[i].v);
            }
        }
    }
    vector<vector<int>> dp(2001, vector<int>(s + 1));
    for (int i = 1; i < 2001; i++) {
        for (int j = 0; j <= s; j++) {
            int val = dp[i - 1][j];
            int weight = j;
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            for (int z = 0; z < value[i].size(); z++) {
                weight += i;
                if (weight > s) {
                    break;
                }
                val += value[i][z];
                dp[i][weight] = max(dp[i][weight], val);
            }
        }
    }
    int m = 0;
    for (int i = 0; i <= 2000; i++) {
        m = max(m, dp[s][i]);
    }
    cout << m << "\n";
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:51:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |         if (value[vec[i].w].size() < s / vec[i].w) {
      |             ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
knapsack.cpp:64:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             for (int z = 0; z < value[i].size(); z++) {
      |                             ~~^~~~~~~~~~~~~~~~~

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