제출 #967767

#제출 시각아이디문제언어결과실행 시간메모리
967767GurbanKnapsack (NOI18_knapsack)C++17
49 / 100
2 ms2432 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int s, mn; vector<ll> dp; vector<int> V, W; vector<vector<pair<int, int>>> u; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int S, n; cin >> S >> n; u.assign(S + 1, {}); while (n--) { int v, w, k; cin >> v >> w >> k; u[w].push_back({v, k}); } for (int i = 1; i <= S; i++) { if (u[i].empty()) continue; sort(u[i].rbegin(), u[i].rend()); s = S / i; for (auto j : u[i]) { mn = min(s, j.second); while (mn--) { V.push_back(j.first); W.push_back(i); } s -= mn; if (!s) break; } } assert((int)V.size() <= 40000); dp.assign(S + 1, -1); dp[0] = 0; for (int i = 0; i < (int)V.size(); i++) { for (int j = S; j >= W[i]; j--) if (j - W[i] >= 0 && j - W[i] <= S && dp[j - W[i]] != -1) dp[j] = max(dp[j], dp[j - W[i]] + V[i]); } ll mx = 0; for (auto i : dp) mx = max(mx, i); cout << mx; }
#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...