Submission #875702

#	Time	Username	Problem	Language	Result	Execution time	Memory
875702		tinnhiemnn	Knapsack (NOI18_knapsack)	C++14	100 / 100	107 ms	75348 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define file "file"
#define pll pair<long long, long long>
const long long N=3000, INF=1e9;
long long W,n,i,j,k,v,w,sum,t,dem,dp[N][N],res;
vector<pll> a[N];

int main()
{
    //freopen(file".inp", "r", stdin);
    //freopen(file".out", "w", stdout);
    ios_base::sync_with_stdio(); cin.tie();

    cin>>W>>n;
    for (i=1;i<=n;i++)
    {
        cin>>v>>w>>k;

        if (w<=W && k>0) a[w].push_back({v, k});
    }

    memset(dp, -0x3f, sizeof dp);
    dp[0][0]=0; i=1;

    for (w=1;w<=W;w++)
    {
        if (a[w].size()==0) continue;
        sort(a[w].begin(), a[w].end(), greater<pll>());

        for (j=0;j<=W;j++)
        {
            dp[i][j]=dp[i-1][j];

            sum=0; t=0; k=0; dem=0;

            while ((sum+1)*w <= j && k<a[w].size())
            {
                sum++;
                t+=a[w][k].first; dem++; //cout<<w<<' '<<j<<' '<<k<<' '<<dem<<'\n';

                dp[i][j]=max(dp[i][j], dp[i-1][j-sum*w] + t);

                if (dem==a[w][k].second) k++, dem=0;
            }
            res=max(res, dp[i][j]);
        }
        i++;
    }

    cout<<res;





}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:37:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             while ((sum+1)*w <= j && k<a[w].size())
      |                                      ~^~~~~~~~~~~~

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