Submission #1307984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307984		hectormedrano	Knapsack (NOI18_knapsack)	C++20	0 / 100	1 ms	1088 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
typedef int ll;

vector<vector<ll>> DP;
vector<vector<pair<ll, ll>>> b;
vector<pair<ll, ll>> a;

ll calc(ll w, ll x){
    if(DP[w][x] != -1){return DP[w][x];}
    if(x==0){return DP[w][x] = 0;}
    if(w<a[x].first){return DP[w][x] = calc(w, x-1);}
    return DP[w][x] = max(calc(w-a[x-1].first, x-1)+a[x-1].second, calc(w, x-1));
}

int main() {
	ll S, N, v, w, k;
    cin>>S>>N;
    b.resize(S+1);
    for(ll i=0;i<N;i++){
        cin>>v>>w>>k;
        b[w].push_back({-v, k});
    }
    for(ll i=1;i<S;i++){
        sort(b[i].begin(), b[i].end());
        if(b[i].size() == 0){continue;}
        ll ind = 0;
        k = b[i][ind].second;
        for(ll j=i;j<=S;j+=i){
            a.push_back({i, -b[i][ind].first});
            k--;
            if(k==0){
                ind++;
                if(ind == b[i].size()){break;}
                k = b[i][ind].second;
            }
        }
    }
    //for(pair<ll, ll> p : a){cout<<p.first<<" "<<p.second<<endl;}
    DP.resize(S+1, vector<ll>(a.size()+1, -1));
    cout<<calc(S, a.size());
}

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