Submission #853136

#	Time	Username	Problem	Language	Result	Execution time	Memory
853136		rarex	Knapsack (NOI18_knapsack)	C++14	100 / 100	84 ms	6248 KiB

knapsack

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;

const int nmax = 2e5;

unordered_map<int,int>mp;
vector<pair<int,int>>knap;
int dp[3][nmax];

struct str
{
    int val;
    int w;
    int k;
}v[nmax];

bool cmp(str a, str b)
{
    if(a.w == b.w)
        return a.val > b.val;
    return a.w > b.w;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,s,i,j;
    cin >> s >> n;
    for(i=1;i<=n;i++)
        cin >> v[i].val >> v[i].w >> v[i].k;
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++)
    {
        int ct = 0;
        while(mp[v[i].w] + v[i].w <= s && ct < v[i].k)
        {
            knap.push_back({v[i].val,v[i].w});
            ct++;
            mp[v[i].w] += v[i].w;
        }
    }
    if(knap.size() >= 30000)
        while(true);
    dp[0][0] = 0;
    for(i = 0; i < knap.size(); i++)
    {
        for(j=1;j<=s;j++)
        {
            dp[1][j] = max(dp[1][j], dp[0][j]);
            if(j >= knap[i].second)
                dp[1][j] = max(dp[1][j], dp[0][j - knap[i].second] + knap[i].first);
        }
        for(j=1;j<=s;j++)
        {
            dp[0][j] = dp[1][j];
            dp[1][j] = 0;
        }
    }
    cout << dp[0][s];
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(i = 0; i < knap.size(); i++)
      |                ~~^~~~~~~~~~~~~

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