| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 463603 | Duy_e | Knapsack (NOI18_knapsack) | C++14 | 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.
/*THINK GONNA FAIL ? IF U DIDNT FAIL THEN WHAT IS THE POINT OF LEARNING */
#include <bits/stdc++.h>
#define ll long long
#define pii pair<long long, long long>
#define ull unsigned long long
#define st first
#define nd second
#define lower_case_alphabet "abcdefghijklmnopqrstuvwxyz"
#define upper_case_alphabet "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define file "test"
using namespace std;
const long long oo = 1e18;
const long long N = 1e5 + 5;
ll s, n, cnt, dp[N], A[N];
vector <pii> d[2004];
void decompose(int x){
if (x == 0){
cnt = -1;
return;
}
cnt = 0;
ll sum = 1;
while (x > sum){
x -= sum;
A[cnt++] = sum;
sum <<= 1;
}
A[cnt] = x;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> s >> n;
for (int i = 1, v, w, k; i <= n; i ++){
cin >> v >> w >> k;
k = min(k, s);
d[w].push_back({v, k});
}
for (int i = 0; i <= s; i ++)
if (d[i].size())
for (pii p: d[i]){
decompose(p.nd);
for (ll W, V; cnt >= 0; cnt --){
W = A[cnt]*i, V = A[cnt]*p.st;
for (int j = s; j >= W; j --)
dp[j] = max(dp[j], dp[j-W] + V);
}
}
cout << dp[s];
return 0;
}
// sketch out every idea before see any solution, it helps alots.
/** /\_/\
* (= ._.)
* / >0 \>1
**/