제출 #696870

#제출 시각아이디문제언어결과실행 시간메모리
696870phongcdKnapsack (NOI18_knapsack)C++14
73 / 100
155 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, f[N][2005]; vector <int> decompose(int x) { int t = 1; vector <int> 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); cin >> m >> n; for (int i = 1; i <= n; i ++) { ll v, w, k; cin >> v >> w >> k; k = min(k, m / w + 1); vector <int> b = decompose(k); for (auto k: b) for (int j = m; j >= k * w; j --) f[i][j] = max(f[i][j], max(f[i][j - k * w], f[i - 1][j - k * w]) + k * v); for (int 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...