Submission #1106168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106168		MytHz1	Knapsack (NOI18_knapsack)	C++14	100 / 100	77 ms	36432 KiB

knapsack

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef pair<int,int>pii;
typedef vector<bool>vb;
typedef __gnu_pbds::tree<int, __gnu_pbds::null_type, less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set;


//for vectors
#define sz(x) int(size(x))
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sor(x) sort(all(x))
#define rsor(x) sort(rall(x))
#define rsz resize
#define ins insert
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()
#define endl '\n'




struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

void solve(){
        ll s,n;cin>>s>>n;
        map<ll,vector<pair<ll,ll>>>mp;//wt ->vector(<value,copy);
        for(int i = 0;i<n;i++){
            ll wt,val,cp;cin>>val>>wt>>cp;
            if(wt <= s && cp > 0){
                if(mp.find(wt) == mp.end()){
                    mp[wt] = {};
                }
                mp[wt].pb({val,cp});
            }
        }
        
        // for(auto x : mp){
        //     cout<<x.first<<" : wt"<<endl;
        //     for(auto y : x.second){
        //         cout<<y.first<<" "<<y.second<<endl;
        //     }
        // }


        // dp[i][j] = most value with j weight and i indices.
        vector<vll> dp(mp.size() + 1,vll(s + 1,INT32_MIN));
        dp[0][0] = 0;
        ll at = 1;
        for(auto it : mp){
            ll w = it.first;
            vector<pair<ll,ll>>items = it.second;
            sort(all(items),greater<pair<ll,ll>>());
            
            for(ll i = 0;i <= s;i++){
                dp[at][i] = dp[at - 1][i];
                ll cp = 0,typeAt = 0,curUsed = 0,profit = 0;
                while((cp + 1)*w <= i && typeAt < items.size() ){
                    cp++;
                    profit += items[typeAt].first;
                    if(dp[at - 1][i - cp*w] != INT32_MIN){
                        dp[at][i] = max(dp[at][i],dp[at - 1][i - cp*w] + profit);
                    } 
                    
                    curUsed++;

                    if(curUsed == items[typeAt].second){
                        curUsed = 0;
                        typeAt++;
                    }
                        
                    
                    
                }
            }


            at++;
        }
        // for(int i =1;i <= mp.size();i++){
        //     for(int j = 0;j <= s;j++){
        //         cout<<dp[i][j]<<" ";
        //     }cout<<"NL"<<endl;
        // }
        ll maxv = 0;
        for(ll wt = 0;wt <= s;wt++){
            maxv = max(maxv,dp[mp.size()][wt]);
        }
        cout<<maxv<<endl;

    }
int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    int tc = 1;
    while(tc--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:81:49: 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]
   81 |                 while((cp + 1)*w <= i && typeAt < items.size() ){
      |                                          ~~~~~~~^~~~~~~~~~~~~~

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