Submission #1201897

#TimeUsernameProblemLanguageResultExecution timeMemory
1201897durgeshhKnapsack (NOI18_knapsack)C++20
100 / 100
62 ms34376 KiB
#include <bits/stdc++.h> #define Task "Task" #define ll long long #define vii vector<pair<ll,ll>> using namespace std; int n,S,w,v,k; map<int,vii> by_weight; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(Task".inp","r")) { freopen(Task".inp","r",stdin); freopen(Task".out","w",stdout); } cin >> S >> n; for(int i = 0; i < n; i++) { cin >> v >> w >> k; if (w <= S && k > 0) by_weight[w].push_back({v,k}); } vector<vector<ll>> best(by_weight.size() + 1, vector<ll> (S + 1, -1e9)); // best[i][j]: best value u can get by using first i types, and j weights best[0][0] = 0; int at = 1; for(auto &[w, items]: by_weight) { sort(items.begin(), items.end(),greater<pair<ll,ll>>()); for(int j = 0; j <= S; j++) { best[at][j] = best[at-1][j]; ll profit = 0; int type_at = 0; int copies = 0; int curr_used = 0; while((copies + 1) * w <= j && type_at < items.size()) { ++copies; profit += items[type_at].first; best[at][j] = max(best[at][j], best[at-1][j - copies * w] + profit); curr_used++; if (curr_used == items[type_at].second) { curr_used = 0; type_at++; } } } at++; } cout << *max_element(best.back().begin(), best.back().end()); return 0; }

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:14:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         freopen(Task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:15:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         freopen(Task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...