Submission #653502

#	Time	Username	Problem	Language	Result	Execution time	Memory
653502		Minhho	Knapsack (NOI18_knapsack)	C++17	100 / 100	62 ms	4948 KiB

knapsack

#define taskname "13"
#include <bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define ff first
#define ss second

using namespace std;
const int maxn = 2010;
vector<ii> a[maxn];
ii b[15*maxn];
int dp[maxn], s, n, cnt = 0;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>s>>n;
    for (int i=1, v, w, k; i<=n; i++) cin>>v>>w>>k, a[w].emplace_back(v, k);
    for (int i=1; i<=s; i++)
    {
        sort(a[i].begin(), a[i].end(), greater<ii>());
        int dem = s/i;
        for (auto [v, k]: a[i])
        {
            if (!dem) break;
            for (int j=1; j<=min(k, dem); j++) b[++cnt] = {v, i};
            dem -= min(k, dem);
        }
    }
    for (int i=1; i<=cnt; i++)
        for (int wt=s; wt>=b[i].ss; wt--)
            if (dp[wt - b[i].ss] || wt == b[i].ss) dp[wt] = max(dp[wt], dp[wt-b[i].ss] + b[i].ff);
    cout<<*max_element(dp+1, dp+s+1);
}

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