Submission #863130

#TimeUsernameProblemLanguageResultExecution timeMemory
863130KodikKnapsack (NOI18_knapsack)C++17
0 / 100
1 ms604 KiB
#include <bits/stdc++.h> using namespace std; // // #define xx real() // #define yy imag() // #define ff first #define ss second // typedef long long ll; typedef long double ld; // typedef complex<ld> point; void sieve(int n, vector<bool>& is_composite, vector<int>& prime) { for (int i = 2; i < n; ++i) { if (!is_composite[i]) prime.push_back(i); for (int j = 0; j < int(prime.size()) && i * prime[j] < n; ++j) { is_composite[i * prime[j]] = true; if (i % prime[j] == 0) break; } } } void setIO(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } int main() { ios_base::sync_with_stdio(0), cin.tie(0); // setIO("shuffle"); int limit, type_num; cin >> limit >> type_num; map<int, vector<pair<int,int>>> by_weight; for(int i = 0; i < type_num; ++i){ int value, weight, amt; cin >> value >> weight >> amt; if(weight <= limit && amt > 0){ by_weight[weight].push_back({value, amt}); } } vector<vector<ll>> best(by_weight.size()+1, vector<ll>(limit+1, INT32_MIN)); best[0][0] = 1; int at = 1; for(auto &[w, items] : by_weight){ sort(items.begin(), items.end(), greater<pair<int,int>>()); for(int i = 0; i <= limit; ++i){ best[at][i] = best[at-1][i]; int copies = 0, type_at = 0, curr_used = 0; ll profit = 0; while((copies+1)*w<=i&&type_at<items.size()){ ++copies; profit += items[type_at].ff; if(best[at-1][i-copies*w]!=INT32_MIN){ best[at][i] = max(best[at][i], best[at-1][i-copies*w]+profit); } ++curr_used; if(curr_used==items[type_at].ss){ curr_used = 0; ++type_at; } } } ++at; } cout << *max_element(best[type_num].begin(), best[type_num].end()) << '\n'; return 0; }

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:54:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    while((copies+1)*w<=i&&type_at<items.size()){
      |                           ~~~~~~~^~~~~~~~~~~~~
knapsack.cpp: In function 'void setIO(std::string)':
knapsack.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     freopen((s + ".out").c_str(), "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...