Submission #720459

#	Time	Username	Problem	Language	Result	Execution time	Memory
720459		mc061	Knapsack (NOI18_knapsack)	C++17	100 / 100	82 ms	2808 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

#ifndef my_dbg
    #define dbg(...) 1337
#else
    #include "debug.h"
#endif 

const long long mod=1e9+7,inf=2e9+228,infll=LLONG_MAX-1e9;

typedef long long ll;
typedef long double ld;

template<typename T, typename Q> ll binPow(T n,Q k) {ll res=1,a=(ll)n,b=(ll)k;while((ll)b){if(b&1)--b,(res*=(ll)a)%=mod;b>>=1,(a*=a)%=mod;}return res;}
template<typename T>istream&operator>>(istream&is,vector<T>&vec){for(T&element:vec){is>>element;}return is;}
template<typename T>ostream&operator<<(ostream&os,vector<T>&vec){for(ll i=0;i+1<vec.size();++i){os<<vec[i]<<" ";}if(vec.size()>0)os<<vec.back();return os;}
template<typename T>void chmin(T&x,T y){x=min(x,y);}
template<typename T>void chmax(T&x,T y){x=max(x,y);}

#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define open_files freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

void solve() {
    ll s, n;
    cin >> s >> n;

    vector<vector<pair<ll, ll>>> by_weight(s + 1);

    for (ll i = 0; i < n; ++i) {
        ll v, w, k;
        cin >> v >> w >> k;
        by_weight[w].push_back({v, k});
    }

    for (ll i = 1; i <= s; ++i) {
        sort(rall(by_weight[i]));
    }

    vector<vector<ll>> newBw(s + 1);
    for (ll weight = 1; weight <= s; ++weight) {
        ll sizeLimit = s / weight + 1;
        for (ll j = 0; j < by_weight[weight].size(); ++j) {
            if (newBw[weight].size() >= sizeLimit) break;
            while (by_weight[weight][j].second > 0 && newBw[weight].size() < sizeLimit) {
                by_weight[weight][j].second--;
                newBw[weight].push_back(by_weight[weight][j].first);
            }
        }
    }


    vector<ll> knapsack(s + 1, -infll);

    knapsack[0] = 0;
    for (ll grab = 1; grab <= s; ++grab) {
        for (ll v : newBw[grab]) {
            for (ll weight = s; weight >= grab; --weight) {
                if (knapsack[weight - grab] == -infll) continue;
                knapsack[weight] = max(knapsack[weight], knapsack[weight - grab] + v);   
            }
        }
    }

    cout << *max_element(all(knapsack)) << "\n";
}

signed main() {
    
    fast_io

#ifdef my_dbg
    open_files
    auto TIME_START = chrono::high_resolution_clock::now();
#endif
    
    cout << fixed << setprecision(25);
    solve();
    
#ifdef my_dbg
    auto TIME_FINISH = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<std::chrono::nanoseconds>(TIME_FINISH-TIME_START).count();
    cerr << "Compiled in: ~";
    if (duration / 1e9 < 1) cerr << duration / 1e6 << "ms.\n";
    else cerr << duration / 1e9 << "s.\n";
#endif
    
}
    
/*
    
day 1 no lean
author: 160cm
created on: April 07, Friday
    
*/

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:46:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (ll j = 0; j < by_weight[weight].size(); ++j) {
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:47:38: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   47 |             if (newBw[weight].size() >= sizeLimit) break;
      |                 ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
knapsack.cpp:48:76: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   48 |             while (by_weight[weight][j].second > 0 && newBw[weight].size() < sizeLimit) {
      |                                                       ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

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