Submission #1154748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154748		vicvic	Knapsack (NOI18_knapsack)	C++20	100 / 100	99 ms	6708 KiB

knapsack

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdint>
#define int long long
using namespace std;
ifstream f ("test.in");
ofstream g ("test.out");
const int NMAX=1e5, WMAX=2e3, KMAX=1e9;
int n, gmax, dp[2005];
struct item
{
    int v, w, c;
    bool operator <(const item a) const
    {
        return v>a.v;
    }
};
vector <item> vec[2005];
item v[100005];
vector <item> list;
int32_t main ()
{
    ios :: sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> gmax >> n;
    int t=0;
    for (int i=1;i<=n;i++)
    {
        cin >> v[i].v >> v[i].w >> v[i].c;
        vec[v[i].w].push_back (v[i]);
    }
    for (int i=1;i<=gmax;i++)
    {
        if (vec[i].empty())
            continue;
        sort (vec[i].begin(), vec[i].end());
        for (int j=0;j<vec[i].size() && j<=gmax/i;j++)
        {
            list.push_back (vec[i][j]);
        }
    }
    for (auto chestie : list)
    {
        int v=chestie.v, c=chestie.c, w=chestie.w;
        int pw=1;
        while (pw<=c)
        {
            for (int i=gmax;i>=w*pw;i--)
            {
                dp[i]=max (dp[i], dp[i-w*pw]+v*pw);
            }
            c-=pw;
            pw*=2;
        }
        for (int i=gmax;i>=c*w;i--)
        {
            dp[i]=max (dp[i], dp[i-c*w]+v*c);
        }
    }
    cout << dp[gmax];
    return 0;
}

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