Submission #570877

#	Time	Username	Problem	Language	Result	Execution time	Memory
570877		Quan2003	Knapsack (NOI18_knapsack)	C++17	100 / 100	175 ms	36356 KiB

knapsack

#include <bits/stdc++.h>
#include <iostream>
#include<queue>
#include<vector>
#include<utility>
using namespace std;
typedef long long ll;
const int sz=2001;
const int sz1=1e5+1;
ll n,x,k,i,j,w,m,high,track;
vector<pair<ll,ll>>a;
ll dp[sz][sz];
int main(){
   cin>>w>>n;
   map<ll,vector<array<ll,2>>>wei;
   for(int i=0;i<n;i++){
       ll t,u,v;cin>>t>>u>>v;
       high=max(high,u);
       if(u<=2000 and v>0) wei[u].push_back({t,v});
   }  for(int i=1;i<=w;i++){
       for(int j=0;j<=w;j++){
           dp[i][j]=INT_MIN;
       }
   } int prev,poi; prev=poi=0; 
     for(auto [we,at]:wei){
         sort(at.rbegin(),at.rend());poi=we-1;
         for(int i=0;i<=w;i++){
            dp[poi][i]=dp[prev][i];
            dp[poi+1][i]=dp[prev][i];
            ll profit,used,cops;
            profit=used=x=0; cops=1;
            while(x<at.size() and cops*we<=i){
               ll y=i-cops*we;
               profit+=at[x][0];
               if (dp[we-1][y]!=INT_MIN){
                   dp[we][i]=max(dp[we][i],dp[we-1][y]+profit);
               } 
               used++;cops++;
               if (used==at[x][1]){x++; used=0;}
            } 
         } prev=we; 
   } cout<<dp[high][w]<<endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:32:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             while(x<at.size() and cops*we<=i){
      |                   ~^~~~~~~~~~

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