Submission #526862

#	Time	Username	Problem	Language	Result	Execution time	Memory
526862		elesis	Knapsack (NOI18_knapsack)	C++14	100 / 100	66 ms	4952 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);
#define int long long 
#define pii pair<int,int> 
#define ff first
#define ss second
const int inf=1e9+7;
const int S=2007;
int dp[2007];
vector <pii> arr[2007];
//dp[i][j] represents the maximum value which can be obtained after choosing i objects with a total weight of j.
void solve()
{
    int N,W,ans=INT_MIN;
    cin>>W>>N;
        for(int i=0;i<N;i++)
    {
        int u,v,e;
        cin>>u>>v>>e;
        arr[v].push_back({u,e});
    }
    for(int i=1;i<=W;i++)
    {
        sort(arr[i].begin(),arr[i].end(),greater <pii> ());
        int cur=0; //the object we're traversing with weight i.
        for(int j=0;j<W/i;j++)
        {
            if(cur>=arr[i].size())
            {
                break;
            }
            for(int k=W;k>=i;k--)
            {
                dp[k]=max(dp[k],dp[k-i]+arr[i][cur].first);
                ans=max(ans,dp[k]);
            }
            arr[i][cur].second--;
            if(arr[i][cur].second==0) cur++;
        }
    }
    cout << ans << "\n";
}
signed main()
{
    fast
    clock_t start, end;
    start = clock();
    solve();
    end = clock();
    double time_taken=double(end-start)/double(CLOCKS_PER_SEC);
    //cout << "time taken" << " " << time_taken << "\n";
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:29:19: 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]
   29 |             if(cur>=arr[i].size())
      |                ~~~^~~~~~~~~~~~~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:51:12: warning: unused variable 'time_taken' [-Wunused-variable]
   51 |     double time_taken=double(end-start)/double(CLOCKS_PER_SEC);
      |            ^~~~~~~~~~

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