Submission #1165498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165498		enzy	Knapsack (NOI18_knapsack)	C++20	100 / 100	39 ms	1892 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
const int maxs=2e3+10;
vector<pair<int,int>>op[maxs];
int dp[maxs];
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int s, n; cin >> s >> n;
    for(int i=1;i<=n;i++){
        int a, b, c; cin >> a >> b >> c;
        op[b].push_back({a,c});
    }
    vector<pair<int,int>>process;
    for(int i=1;i<=s;i++){
        int m=(s/i), at=1;
        sort(op[i].begin(),op[i].end());
        while(at<=m&&op[i].size()){
            at++;
            int sz=op[i].size()-1;
            op[i][sz].second--;
            process.push_back({op[i].back().first,i});
            if(op[i][sz].second==0) op[i].pop_back();
        }
    }
    int resp=0;
    for(auto p : process){
        for(int i=s;i>=p.second;i--){
            dp[i]=max(dp[i],dp[i-p.second]+p.first);
            resp=max(resp,dp[i]);
        }
    }
    cout << resp << endl;
    return 0;
}

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