Submission #1203026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203026		bahaktl	Knapsack (NOI18_knapsack)	C++20	73 / 100	435 ms	327680 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

#define sz size()
#define nah "No\n"
#define yeah "Yes\n"
#define F first 
#define S second 
#define int long long
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const int inf=1e13;
const int N=100000+23;
const int mod=1e9+7;

int dp[2001*2001],w[N],c[N],a[N];

signed main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    // freopen("snakes.in","r",stdin);
    // freopen("snakes.out","w",stdout);
    int n,k;
    cin>>k>>n;
    vector<pair<int,int>>v;
    for(int i=1;i<=n;i++) {
        cin>>c[i]>>w[i]>>a[i];
        if(w[i]>k){
            continue;
        }
        int sum=w[i];
        while(sum<=k && a[i]--) {
            v.pb({w[i],c[i]});
            sum+=w[i];
        }
    }
    for(auto [weight,val]:v) {
        for(int j=k;j>=weight;j--) {
            dp[j]=max(dp[j],dp[j-weight]+val);
        }
    }
    int ans=-inf;
    for(int i=1;i<=k;i++) {
        ans=max(ans,dp[i]);
    }
    cout<<ans;
}

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