Submission #1017395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017395		Madhav_1608	Knapsack (NOI18_knapsack)	C++17	100 / 100	42 ms	7480 KiB

knapsack

using namespace std;
#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
// #include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template <class T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<long long int> vll;
typedef pair<ll,ll> pll;
#define FOR(i,a,b) for(long long int i=a;i<b;i++)
#define all(v) v.begin(),v.end()
template <typename I>
void print(vector<I> &v){
    FOR(i,0,v.size()-1){cout << v[i] << " ";}
    cout << v.back() << "\n";
}
ll gcd(ll a,ll b){
    if(a==0){return b;}
    else if(b==0){return a;}
    else if(a<b){return gcd(b%a,a);}
    else{return gcd(a%b,b);}
}
ll lcm(ll a,ll b){
    return (a/gcd(a,b))*b;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll s,n;
    cin >> s >> n;
    vll v(n);
    vll w(n);
    vll k(n);
    FOR(i,0,n){
        cin >> v[i] >> w[i] >> k[i];
    }
    vector<vector<pll>> weights(s+1);
    FOR(i,0,n){
        weights[w[i]].push_back({v[i],k[i]});
    }
    FOR(i,1,s+1){
        if(!weights[i].empty()){
            sort(all(weights[i]));
        }
    }
    vll total(s+1,0);
    FOR(i,1,s+1){
        FOR(j,0,weights[i].size()){
            total[i] += weights[i][j].second;
        }
    }
    vll ans(s+1,-1);
    ans[0] = 0;
    FOR(i,1,s+1){
        ll curr = weights[i].size()-1;
        ll madhav = min(s/i,total[i]);
        FOR(j,0,madhav){
            if(weights[i][curr].second==0){
                curr--;
            }
            for(ll m=s;m>=i;m--){
                if(ans[m-i]!=-1){
                    ans[m] = max(ans[m],ans[m-i]+weights[i][curr].first);
                }
            }
            weights[i][curr].second--;
        }
    }
    cout << *max_element(all(ans)) << "\n";
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:26: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]
   26 | #define FOR(i,a,b) for(long long int i=a;i<b;i++)
......
   65 |         FOR(j,0,weights[i].size()){
      |             ~~~~~~~~~~~~~~~~~~~~~          
knapsack.cpp:65:9: note: in expansion of macro 'FOR'
   65 |         FOR(j,0,weights[i].size()){
      |         ^~~

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