Submission #1203032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203032		bahaktl	Knapsack (NOI18_knapsack)	C++20	73 / 100	348 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];

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;
    map<pair<pair<int,int>,int>,int>mp;
    vector<pair<int,int>>v;
    for(int i=1;i<=n;i++) {
        pair<pair<int,int>,int> b;
        int c,w,a;
        cin>>c>>w>>a;
        b.F.F=c;
        b.F.S=w;
        b.S=a;
        if(w>k || mp[b]){
            continue;
        }
        int sum=w;
        while(sum<=k && a--) {
            v.pb({w,c});
            sum+=w;
        }
        mp[b]=true;
    }
    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