Submission #1015796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015796		catsarecool5530	Knapsack (NOI18_knapsack)	C++17	100 / 100	43 ms	3676 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl "\n"
const ll MOD = 998244353;
void setIO() { freopen("input.in", "r", stdin); }
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
	//setIO();
    
    int s, n; cin >> s >> n;

    vector<ll> dp(s+1, -1);
    dp[0] = 0;
    vector<vector<pair<int, int>>> weights(s+1);
    // weights[weight] = vector of all the weights dummy[index] = {value, amount}
    for (int i = 0; i < n; i++) {
        int value, weight, amount; cin >> value >> weight >> amount;
        weights[weight].push_back({value, amount});
    }
    for (vector<pair<int, int>>& i : weights) {
        sort(i.begin(), i.end(), [](pair<int, int> a, pair<int, int> b) {return a.first > b.first;});
    }
    //cout << weights[1][0].first << endl;
    ll ans = 0;
    for (int weight = 1; weight <= s; weight++) {
        for (int index = s; index >= 0; index--) {
            if (dp[index] == -1) continue;
            int curTot = index;
            for (int weightIndex = 0; weightIndex < weights[weight].size(); weightIndex++) {
                //int takeFrom = curTot;
                for (int amountUsed = 1; amountUsed <= weights[weight][weightIndex].second; amountUsed++) {
                    curTot += weight;
                    if (curTot > s) goto end;
                    dp[curTot] = max(dp[curTot], dp[curTot - weight] + weights[weight][weightIndex].first);
                    ans = max(dp[curTot], ans);
                }
            }
            end:;
        }
    }
    cout << ans << endl;


    


    

}

    
    

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:37:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for (int weightIndex = 0; weightIndex < weights[weight].size(); weightIndex++) {
      |                                       ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp: In function 'void setIO()':
knapsack.cpp:6:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | void setIO() { freopen("input.in", "r", stdin); }
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp: In function 'void setIO(std::string)':
knapsack.cpp:8:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:9:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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