Submission #1023961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023961		CoolD	Knapsack (NOI18_knapsack)	C++14	100 / 100	173 ms	125088 KiB

knapsack

#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vpi vector<pair<int,int>>

using namespace std;

int main()
{
    int s, n;
    cin >> s >> n;
    vector<vpi> item(s+1);
    for (int i = 0; i < n; i++)
    {
        int v, w, k;
        cin >> v >> w >> k;
        item[w].push_back({v, k});
    }
    for (int i = 0; i <= s; i++)
    {
        sort(item[i].begin(), item[i].end(), greater<pair<int, int>>());
    }
    vpi collection;
    for (int i = 1; i <= s; i++)
    {
        // for ith weight make sum upto s
        int w = 0;
        for (auto &&p : item[i])
        {
            int v = p.first;
            int k = p.second;
            while (k--)
            {
                if(w+i <= s)
                {
                    w += i;
                    collection.push_back({i, v});
                }
                else
                    break;
            }
            if(w+i > s)
                break;            
        } 
    }
    int m = collection.size();
    int dp[m][s+1];
    memset(dp, 0, sizeof dp);
    dp[0][collection[0].first] = collection[0].second;
    for (int i = 1; i < m; i++)
    {
        for (int w = 1; w <= s; w++)
        {
            dp[i][w] = dp[i-1][w];
            int x = collection[i].first;
            int v = collection[i].second;
            if(w >= x)
                dp[i][w] = max(dp[i][w], dp[i-1][w-x]+v);
        }
    }
    int ans = 0;
    for (int w = 0; w <= s; w++)
    {
        ans = max(dp[m-1][w], ans);
    }
    cout << ans << endl;   
}

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