Submission #845037

#TimeUsernameProblemLanguageResultExecution timeMemory
845037taimoitapcode1Knapsack (NOI18_knapsack)C++17
100 / 100
108 ms35152 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long ll oo = 1e18 + 7, res = 0; int limit, n; vector<pair<int, int>> weight[2005]; ll dp[2005][2005]; int main(){ cin >> limit >> n; for (int i = 1; i <= n; i++){ int weigh, value, cnt; cin >> value >> weigh >> cnt; weight[weigh].push_back({value, cnt}); } for (int i = 1; i <= limit; i++) sort(weight[i].begin(), weight[i].end(), greater<pair<int, int>>()); for (int i = 0; i <= limit; i++){ for (int cost = 0; cost <= limit; cost++) dp[i][cost] = -oo; } dp[0][0] = 0; for (int i = 1; i <= limit; i++){ for (int cost = 0; cost <= limit; cost++){ int index = 0; int cnt = 1; int typee = 0; ll hihi = 0; dp[i][cost] = dp[i - 1][cost]; while(cnt * i <= cost && typee < weight[i].size()){ hihi += weight[i][typee].fi; if(dp[i - 1][cost - cnt * i] != oo) dp[i][cost] = max(dp[i][cost], dp[i - 1][cost - cnt * i] + hihi); res = max(res, dp[i][cost]); index++; cnt++; if(index == weight[i][typee].se){ index = 0; typee++; } } } } cout << res; }

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:42:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             while(cnt * i <= cost && typee < weight[i].size()){
      |                                      ~~~~~~^~~~~~~~~~~~~~~~~~
#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...