제출 #1276026

#제출 시각아이디문제언어결과실행 시간메모리
1276026lee.desmond2016Knapsack (NOI18_knapsack)C++20
100 / 100
68 ms33304 KiB
#include "bits/stdc++.h" using namespace std; #define ll long long const int MOD = 1e9+7; const int INF = 1e9; void solve() { int s, n; cin >> s >> n; map<int, vector<array<int, 2>>> mp; for (int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; if (w <= s) { mp[w].push_back({v, k}); } } vector<vector<ll>> dp(mp.size() + 1, vector<ll>(s + 1, -1)); dp[0][0] = 0; int idx = 1; for (auto [w, v] : mp) { sort(v.rbegin(), v.rend()); // 0-1 knapsack for (int i = 0; i <= s; i++) { dp[idx][i] = dp[idx - 1][i]; int j = 0; ll sumV = 0; int cnt = 0; int used = 0; while (j < v.size() && (cnt + 1) * w <= i) { cnt++; sumV += v[j][0]; if (dp[idx - 1][i - cnt * w] != -1) { dp[idx][i] = max(dp[idx][i], dp[idx - 1][i - cnt * w] + sumV); } used++; if (used == v[j][1]) { used = 0; j++; } } } idx++; } ll ans = 0; for (int i = 1; i <= s; i++) { ans = max(ans, dp[mp.size()][i]); } cout << ans << '\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); // freopen("input.in", "r", stdin); // freopen("output.out", "w", stdout); // int T = 1; // cin >> T; // while (T--) { solve(); // } return 0; }
#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...