Submission #523511

#	Time	Username	Problem	Language	Result	Execution time	Memory
523511		amin	Knapsack (NOI18_knapsack)	C++14	100 / 100	130 ms	8460 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

long long w[200000],va[200000],t[200000];
long long dp[50000],d[50000];
int main()
{
long n;
long m;
cin>>m;

cin>>n;
vector<pair<long long,long long >>v[50000];
for(long i=0;i<n;i++)
{
 cin>>va[i]>>w[i]>>t[i];
 v[w[i]].push_back({-va[i],t[i]});
}
for(long i=0;i<=m;i++)
{
    sort(v[i].begin(),v[i].end());
}
for(long i=0;i<=m;i++)
{
    for(long y=0 ;y<v[i].size();y++)
    {
        v[i][y].first*=-1;
        //cout<<v[i][y].first;

    }

    dp[i]=-1;
    d[i]=-1;
}
dp[0]=0;
d[0]=0;
long long x=0;
long long sum=0;

for(long i=0;i<=m;i++)
{

    for(long y=0;y<=m;y++)
    {
        dp[y]=d[y];
    }
    if(v[i].size()>0)
    for(long y=0;y<=m;y++)
    {

        if(dp[y]!=-1)
        {
            x=0;
            long long b=0;

            sum=v[i][b].second;

            for(long u=i;u+y<=m;u+=i)
            {
                   x+=v[i][b].first;
                d[y+u]=max(d[y+u],dp[y]+x);

                sum--;
                if(sum<=0)
                {
                    b++;
                    if(b>=v[i].size())
                        break;
                    sum=v[i][b].second;
                }

            }
        }
    }
}
long long ans=0;
for(long i=0;i<=m;i++)
{

    ans=max(ans,d[i]);
}
cout<<ans;






}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:26:20: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(long y=0 ;y<v[i].size();y++)
      |                   ~^~~~~~~~~~~~
knapsack.cpp:68:25: 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]
   68 |                     if(b>=v[i].size())
      |                        ~^~~~~~~~~~~~~

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