Submission #900586

#	Time	Username	Problem	Language	Result	Execution time	Memory
900586		Servant_of_the_Lord	Knapsack (NOI18_knapsack)	C++17	100 / 100	50 ms	5288 KiB

knapsack

#include<bits/stdc++.h>
#define ll long long

using namespace std;

main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll x,y,z,a,b,c;
    cin>>x>>y;
    vector<ll>v(x+1);
    vector<pair<ll,ll>>w;
    vector<vector<pair<ll,ll>>>u(x+1);
    for(ll i=0;i<y;i++)
    {
        cin>>a>>b>>c;
        u[b].push_back({a,c});
    }
    for(ll i=1;i<=x;i++)
    {
        sort(u[i].begin(),u[i].end());
        a=x/i;
        while(u[i].size()&&a>0)
        {
            w.push_back({i,u[i].back().first});
            u[i].back().second--;
            a--;
            if(!u[i].back().second)u[i].pop_back();
        }
    }
    for(auto i:w)
    {
        for(ll j=x;j>=i.first;j--)
        {
            v[j]=max(v[j],v[j-i.first]+i.second);
        }
    }
    cout<<v.back()<<'\n';
}

Compilation message (stderr)

knapsack.cpp:6:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    6 | main()
      | ^~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:10:12: warning: unused variable 'z' [-Wunused-variable]
   10 |     ll x,y,z,a,b,c;
      |            ^

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