Submission #767229

#	Time	Username	Problem	Language	Result	Execution time	Memory
767229		jabeznguyen	Knapsack (NOI18_knapsack)	C++14	100 / 100	116 ms	35152 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;
template<typename T>
using ordered_set = tree<T,null_type,less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define f(i,a,b) for(int i=int (a);i<=int (b);i++)
#define ff(i,a,b) for(int i=int (a);i<int (b);i++)
#define F(i,a,b) for(int i=int (a);i>=int (b);i--)
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define lower(p,x) lower_bound(all(p),x)
#define upper(p,x) upper_bound(all(p),x)
#define ms(a,x) memset(a,x,sizeof (a))
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
const double eps=1e-9,pi=acos(-1.0);
const int N=1e6+6,inf=0x3f3f3f3f,mod=1e9+7;
int main()
{
    int s,n;
    cin>>s>>n;
    map<int,vector<pair<int,int>>> by_weight;
    ff(i,0,n)
    {
        int v,w,k;
        cin>>v>>w>>k;
        by_weight[w].pb({v,k});
    }
    vector<vector<ll>> b(by_weight.size()+1,vector<ll>(s+1,INT32_MIN));
    b[0][0]=0;
    int att=1;
    for(auto &[w,items]: by_weight){
        sort(items.begin(),items.end(),greater<pair<int,int>>());
        for(int i=0;i<=s;i++){
            b[att][i]=b[att-1][i];
            int copies=0;
            int type_att=0;
            ll value=0;
            int cur_used=0;
            while((copies+1)*w<=i&&type_att<items.size()){
                copies++;
                value+=items[type_att].fi;
                if(b[att-1][i-copies*w]!=INT32_MIN)
                    b[att][i]=max(b[att][i],b[att-1][i-copies*w]+value);
                cur_used++;
                if(cur_used==items[type_att].se){
                    type_att++;
                    cur_used=0;
                }
            }
        }
        att++;
    }
    cout<<*max_element(b.back().begin(),b.back().end());
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:44:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |     for(auto &[w,items]: by_weight){
      |               ^
knapsack.cpp:52:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             while((copies+1)*w<=i&&type_att<items.size()){
      |                                    ~~~~~~~~^~~~~~~~~~~~~

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