Submission #1204168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204168		bahaktl	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	70492 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];
int mp[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);
    }
    vector<pair<int,int>>res;
    sort(rall(v));
    for(int i = 0;i < n; i++) {
        int op,pos = min(2000 / v[i].F.S,v[i].S);
        if(mp[v[i].F.S][pos] >= 2000) continue;
        else {
            op = min(max(2000-mp[v[i].F.S][pos],0LL),v[i].S * v[i].F.S);
            mp[v[i].F.S][pos] += op;
        }
        int t=pos;
        while(t--) {
            res.pb({v[i].F.F, v[i].F.S});
        }
        mp[v[i].F.S][pos] += op;
        //cout<<mp[{v[i].F.S,pos}]<<"\n";
    }
    //cout<<res.sz;
    for(auto [val,weight] : res) {
        for(int j = k;j >= weight; j--) {
            dp[j] = max(dp[j],dp[j - weight] + val);
        }
    }
    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