Submission #624308

#TimeUsernameProblemLanguageResultExecution timeMemory
624308pi61Knapsack (NOI18_knapsack)C++14
100 / 100
149 ms17936 KiB
#include <bits/stdc++.h> using namespace std; int s,n,ans; int dp[2005][2005]; struct item { int val,weight,cnt; }; item a[100005]; vector<int> p[2005]; bool comp(item a, item b) { return (a.weight < b.weight or (a.weight == b.weight and a.val > b.val)); } int main() { cin>>s>>n; for (int i = 1; i <= n; i++) { cin>>a[i].val>>a[i].weight>>a[i].cnt; } sort(a+1,a+1+n,comp); for (int i = 1; i <= n; i++) { int w=a[i].weight,k=a[i].cnt; while (p[w].size() < (s/w) and k > 0) { if (!p[w].empty()) p[w].push_back(a[i].val + p[w].back()); else p[w].push_back(a[i].val); k--; } } for (int i = 1; i <= s; i++) { for (int j = 1; j <= s; j++) { dp[i][j]=dp[i-1][j]; for (int cnt = 0; cnt < p[i].size(); cnt++) { if (j - (cnt + 1)*i < 0) continue; dp[i][j]=max(dp[i][j],dp[i-1][j-(cnt+1)*i] + p[i][cnt]); } ans=max(ans,dp[i][j]); } } // for (int i = 1; i <= s; i++) cout<<p[i].size()<<' ';cout<<endl; // for (int i = 1; i <= s; i++) // { // for (int j = 1; j <= s; j++) // { // cout<<dp[i][j]<<' '; // } // cout<<endl; // } cout<<ans; }

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:26:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |   while (p[w].size() < (s/w) and k > 0)
      |          ~~~~~~~~~~~~^~~~~~~
knapsack.cpp:39:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    for (int cnt = 0; cnt < p[i].size(); cnt++)
      |                      ~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...