Submission #624305

#TimeUsernameProblemLanguageResultExecution timeMemory
624305pi61Knapsack (NOI18_knapsack)C++14
29 / 100
47 ms63124 KiB
#include <bits/stdc++.h> using namespace std; int s,n,ans; pair<int,int> dp[2005][2005][2]; 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 and k > 0) { 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][0].first=dp[i][j][1].first=-1; for (int i = 1; i <= s; i++) { for (int j = 0; j <= s; j++) { for (int bl = 0; bl < 2; bl++) { if (dp[i][j][bl].first == -1) continue; ans=max(ans,dp[i][j][bl].first); int cnt = dp[i][j][bl].second; if (dp[i+1][j][0].first < dp[i][j][bl].first) dp[i+1][j][0].first=dp[i][j][bl].first; if (cnt >= p[i].size() or j + i > s) continue; int nextitem = p[i][cnt]; if (dp[i][j][bl].first + nextitem > dp[i][j + i][1].first) dp[i][j+i][1].first=dp[i][j][bl].first + nextitem, dp[i][j+i][1].second=dp[i][j][bl].second + 1; } } } // 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].first<<','<<dp[i][j].second<<'}'; } 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 and k > 0)
      |          ~~~~~~~~~~~~^~~
knapsack.cpp:44:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     if (cnt >= p[i].size() or j + i > s) continue;
      |         ~~~~^~~~~~~~~~~~~~
#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...