Submission #566160

#	Time	Username	Problem	Language	Result	Execution time	Memory
566160		TheDeliverator	Knapsack (NOI18_knapsack)	C++17	0 / 100	15 ms	31816 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 < 2004; i++) {
        for (int j = 0; j < 2004; j++) {
          dp[i][j] = -1e9;
        }
      }

      for (int i = 0; i < n; i++) {

        int v, w, k;
        cin >> v >> w >> k;
        if (!mp.count(w)) {
          vector <pair<int, int>> temp;
          temp.pb({v, k});
          mp[w] = temp;
        }
        else {
          auto temp = mp[w];
          temp.pb({v, k});
          mp[w] = temp;
        }
      }


      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 <= n; i++) {
        ans = max(ans, dp[i][s]);
      }
      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:130: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]
  130 |           while ((used + 1) * w <= i && type < items.size()) {
      |                                         ~~~~~^~~~~~~~~~~~~~

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