Submission #1203467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203467		bahaktl	Knapsack (NOI18_knapsack)	C++20	73 / 100	383 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;
    vector<pair<pair<int,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;
        v.pb(b);
    }
    map<pair<int,int>,int>mp;
    vector<pair<int,int>>res;
    sort(rall(v));
    for(int i = 0;i < n; i++) {
        int sum = v[i].F.S;
        int op = 2000 / ((int) v[i].F.S);
        if(op > v[i].S) op = v[i].S;
        if(v[i].F.F < mp[{v[i].F.S, op}]) continue;
        while(op--) {
            res.pb({v[i].F.F, v[i].F.S});
        }
        mp[{v[i].F.S,op}] = v[i].S;
    }
    for(auto [weight,val] : res) {
        for(int j = k;j >= val; j--) {
            dp[j] = max(dp[j],dp[j - val] + weight);
        }
    }
    int ans=-inf;
    for(int i = 0;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