제출 #565992

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
565992		TheDeliverator	Knapsack (NOI18_knapsack)	C++11	73 / 100	463 ms	262144 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;
int dp[100005][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;
      vector <int> v[n];
      for (int i = 0; i < n; i++) {
        ll val, w, k;
        cin >> val >> w >> k;
        v[i].pb(val);
        v[i].pb(w);
        v[i].pb(k);
      }


      for (ll i = 1; i <= n; i++) {
        for (ll j = 0; j <= s; j++) {
          dp[i][j] = dp[i - 1][j];
          int tmp = j;
          int times = 1;
          while (tmp - v[i-1][1] >= 0 && times <= v[i-1][2]) {
            dp[i][j] = max(dp[i][j], dp[i - 1][tmp - v[i-1][1]] + times * v[i-1][0]);
            tmp -= v[i-1][1];
            ++times;
          }
        }
      }

      cout << dp[n][s] << "\n";


    }

    void static tsolve() {
      int tests;
      cin >> tests;
      for (int i = 0; i < tests; i++) {
        solve(i);
      }
    }
};


int main() {


    Solver::solve();
    return 0;
}

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