# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1180906 | abdelaal_03 | Knapsack (NOI18_knapsack) | C11 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef long long ll;
const long double PI = 3.141592654;
const long long md = 998244353;
#define xi first
#define yi second
#define MAX 300007
#define INF (ll)1e18
#define SQ 500
long long gcd(long long a, long long b) {
if (b == 0)return a;
return (a % b) ? gcd(b, a % b) : b;
}
ll dp[1007][5000];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ll n, W;
cin>>n>>W;
vector<ll> w(n + 1), v(n + 1), k(n + 1);
for (int i = 1; i<= n; i++) {
ll wi, vi, ki;
cin>>vi>>wi>>ki;
w[i] = wi;
v[i] = vi;
k[i] = ki;
}
for (int i = 1;i <= n; i++) {
set<pair<ll, ll>>s[w[i]];
for (int j = 0; j <= W; j++){
dp[i][j] = dp[i - 1][j];
ll rem = j % w[i];
if (s[rem].size() > k[i]) {
ll idx = j - (k[i] + 1) * w[i];
ll ow = dp[i - 1][idx] * w[i] - idx * v[i];
auto it = s[rem].find({ow, idx});
s[rem].erase(it);
}
if (!s[rem].empty()) dp[i][j] = max(dp[i][j], (s[rem].rbegin()->xi + j * v[i]) / w[i]);
ll nw = dp[i - 1][j] * w[i] - j * v[i];
s[rem].insert({nw, j});
}
}
cout<<dp[n][W]<<endl;
return 0;
}