Submission #985233

#	Time	Username	Problem	Language	Result	Execution time	Memory
985233		Marcus	Knapsack (NOI18_knapsack)	C++17	100 / 100	125 ms	36432 KiB

knapsack

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

void read() {freopen("input.txt", "r", stdin);}

int main() {
    //read();
    ll s, n; cin>>s>>n;
    map<ll, vector<pair<ll, ll>>> p;
    for (ll i=0; i<n; i++)
    {
        int v, w, c; cin>>v>>w>>c;
        p[w].push_back({v, c});
    }

    vector<vector<ll>> dp((ll)p.size()+1, vector<ll>(s+1, 0));
    ll ite = 1;
    for (auto &[w, items]: p)
    {
        sort(items.begin(), items.end(), greater<pair<ll, ll>>());
        for (ll x=1; x<=s; x++)
        {
            dp[ite][x] = dp[ite-1][x];
            ll copy = 0;
            ll item = 0;
            ll item_copy = 0;
            ll profit = 0;
            while((copy+1)*w <= x && item < items.size())
            {
                copy++;
                profit += items[item].first;
                dp[ite][x] = max(dp[ite][x], dp[ite-1][x-copy*w] + profit);
                
                item_copy++;
                if (item_copy == items[item].second) {item_copy = 0; item++;}
            }
        }
        ite++;
    }
    //for (auto u: dp[(ll)p.size()]) {cout<<u<<" ";}
    cout<<dp[(ll)p.size()][s];
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:29:43: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |             while((copy+1)*w <= x && item < items.size())
      |                                      ~~~~~^~~~~~~~~~~~~~
knapsack.cpp: In function 'void read()':
knapsack.cpp:5:21: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void read() {freopen("input.txt", "r", stdin);}
      |              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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