| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 565988 | TheDeliverator | Knapsack (NOI18_knapsack) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 <ll> 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];
ll tmp = j;
ll 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;
}