Submission #566829

#	Time	Username	Problem	Language	Result	Execution time	Memory
566829		Minhho	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	428 KiB

knapsack

#define taskname "Knapsack"
#include <bits/stdc++.h>
#define int long long 
#define ii pair<int,int>

using namespace std;
const int maxn = 2010;
vector<ii> a[maxn], b[maxn];
int dp[maxn], n, S, val[10*maxn], wt[10*maxn];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>S>>n;
    for (int i=1; i<=n; i++)
    {
        int v, w, k;
        cin>>v>>w>>k;
        a[w].emplace_back(v, k);
    }
    int dem = 1;
    for (int i=1; i<=2000; i++) 
    {
        sort(a[i].begin(), a[i].end());
        int cur = 0, up = S/i;
        for (auto [v, k]: a[i])
        {
            if (cur >= up) break;
            if (cur+k <= up) b[i].emplace_back(v, k), cur += k;
            else
            {
                b[i].emplace_back(v, up-cur);
                break;
            }
        }
        for (auto [v, c]: b[i])
        {
            for (int j=dem; j<=dem+c-1; j++) val[j] = v, wt[j] = i;
            dem += c;
        }
    }
    dem--;
    //cout<<dem<<"\n";
    //for (int i=1; i<=dem; i++) cout<<val[i]<<" "<<wt[i]<<"\n";
    for (int i=1; i<=dem; i++)
        for (int weight=S; weight>=wt[i]; weight--)
            if (dp[weight-wt[i]] || weight==wt[i]) 
                dp[weight] = max(dp[weight], dp[weight-wt[i]]+val[i]);
    cout<<*max_element(dp+1, dp+S+1);
}

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