제출 #696859

#제출 시각아이디문제언어결과실행 시간메모리
696859phongcdKnapsack (NOI18_knapsack)C++14
73 / 100
148 ms262144 KiB
#include <bits/stdc++.h> #define ll long long #define ii pair <int, int> #define ill pair <ll, ll> #define fi first #define se second #define all(x) x.begin(), x.end() #define file "test" using namespace std; const int N = 1e5 + 5; const int MOD = 1e9 + 7; const ll INF = 1e18; const int base = 311; const int BLOCK_SIZE = 2000; ll n, m, v[N], w[N], k[N], f[N][2005]; vector <ll> decompose(ll x) { ll t = 1; vector <ll> res; while (x > t) { res.push_back(t); x -= t, t *= 2; } res.push_back(x); return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // #ifndef ONLINE_JUDGE // freopen(file".inp","r",stdin); freopen(file".out","w",stdout); // #endif cin >> m >> n; for (ll i = 1; i <= n; i ++) { cin >> v[i] >> w[i] >> k[i]; vector <ll> b = decompose(k[i]); for (auto k: b) for (ll j = m; j >= k * w[i]; j --) f[i][j] = max(f[i][j], max(f[i][j - k * w[i]], f[i - 1][j - k * w[i]]) + k * v[i]); for (ll j = 1; j <= m; j ++) f[i][j] = max(f[i][j], f[i - 1][j]); } cout << f[n][m]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...