Submission #566166

#TimeUsernameProblemLanguageResultExecution timeMemory
566166TheDeliveratorKnapsack (NOI18_knapsack)C++17
100 / 100
159 ms33188 KiB
#include <map> #include <cstring> #include <iostream> #include <vector> #include <cmath> #include <string> #include <algorithm> #include <cstring> #include <unordered_map> #include <fstream> #include <set> #include <queue> using namespace std; #define ll long long #define pb push_back /* * * Segment Tree implementation * Current implementation: Range Minimum Query * */ template <class T> struct SegTree { /* * TODO: Now the building of the tree is done by updating values which is done in O(NlogN) * TODO: Better understand the maths behind the algorithm * Implement a build function which builds the segment tree from a fixed-size array such that it runs in linear time * */ int init_val = 1e9 + 1; // max value as we want the minimum (used for min segment tree) int tree_size; vector <T> segment; void init(int _n) { tree_size = _n; segment.assign(2 * tree_size + 2, init_val); // +2 to ensure safe space for [0,n] } T combine(T a, T b) { return a + b; // sum queries } void pull(int p) { segment[p] = combine(segment[2 * p], segment[2 * p + 1]); } void update(int p, T val) { // sets val at position p segment[p += tree_size] = val; for (p /= 2; p != 0; p /= 2) { pull(p); } } T query(int l, int r) { // sum on interval [l, r] T ra, rb; ra = rb = 0; for (l += tree_size, r += tree_size + 1; l < r; l /= 2, r /= 2) { if (l & 1) ra = combine(ra, segment[l++]); if (r & 1) rb = combine(segment[--r], rb); } return combine(ra, rb); } }; const int MOD = 1e9+7; const int NMAX = 5000005; //ll dp[2005][2005]; class Solver { public: Solver(){} void static solve(int test) { } void static solve() { //ifstream fin("feast.in"); //ofstream fout("feast.out"); // ll s, n; cin >> s >> n; map<int, vector<pair<int, int>>> mp; for (int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; mp[w].pb({v, k}); } vector <vector <ll>> dp(mp.size() + 1, vector<ll>(s+1, -1e9)); dp[0][0] = 0; int weight_types = 1; for (auto& [w, items] : mp) { sort(items.begin(), items.end(), std::greater<pair<int, int>>()); for (int i = 0; i <= s; i++) { dp[weight_types][i] = dp[weight_types - 1][i]; int curr = 0, type = 0, used = 0; ll profit = 0; while ((used + 1) * w <= i && type < items.size()) { profit += items[type].first; used++; if (dp[weight_types - 1][i - (used) * w] != -1e9) { dp[weight_types][i] = max(dp[weight_types][i], dp[weight_types - 1][i - (used) * w] + profit); } curr++; if (curr == items[type].second) { curr = 0; ++type; } } } weight_types++; } ll ans = 0; for (int i = 0; i <= s; i++) { ans = max(ans, dp[mp.size()][i]); } cout << ans << "\n"; } void static tsolve() { int tests; cin >> tests; for (int i = 0; i < tests; i++) { solve(i); } } }; int main() { Solver::solve(); return 0; }

Compilation message (stderr)

knapsack.cpp: In static member function 'static void Solver::solve()':
knapsack.cpp:116:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |           while ((used + 1) * w <= i && type < items.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...