Submission #566166

#	Time	Username	Problem	Language	Result	Execution time	Memory
566166		TheDeliverator	Knapsack (NOI18_knapsack)	C++17	100 / 100	159 ms	33188 KiB

knapsack

#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()) {
      |                                         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27