Submission #877911

#	Time	Username	Problem	Language	Result	Execution time	Memory
877911		tigar	Knapsack (NOI18_knapsack)	C++14	100 / 100	47 ms	5096 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll s, n;
vector<pair<ll, ll> >w[2020];
ll dp[2020];

bool cmp(pair<ll, ll>a, pair<ll, ll>b)
{
    return a.first>b.first;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); //cout.tie(0);
    cin>>s>>n;
    for(int i=1; i<=n; i++)
    {
        ll val, weight, countt;
        cin>>val>>weight>>countt;
        w[weight].push_back({val, countt});
    }
    for(int i=1; i<=s; i++){sort(w[i].begin(), w[i].end(), cmp); dp[i]=-1;}
    for(int i=1; i<=s; i++)
    {
        for(int j=s; j>=i; j--)
        {
            int k=1, price=0;
            for(int l=0; l<w[i].size(); l++)
            {
                //cout<<"OVDE\n";
                int pff=1;
                while(pff<=w[i][l].second and k*i<=j)
                {
                    if(dp[j-k*i]!=-1)dp[j]=max(dp[j-k*i]+price+pff*w[i][l].first, dp[j]);
                    k++; pff++;
                    //cout<<l<<" "<<j<<endl;
                }
                price+=w[i][l].second*w[i][l].first;
                if(k*i>j)break;
            }
        }
    }
    ll rez=0;
    for(int i=1; i<=s; i++)rez=max(rez, dp[i]);
    cout<<rez;
    return 0;
}

Compilation message (stderr)

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

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