Submission #1171709

#TimeUsernameProblemLanguageResultExecution timeMemory
1171709abcsedafaefKnapsack (NOI18_knapsack)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h> using namespace std; #define vi vector<long long> #define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL) #define ll long long void solve() { ll x, n; cin >> x >> n; vi v_temp, c_temp, t_temp; vector<ll> new_t; map<ll, ll> myMap; for (ll i = 0; i < n; i++) { ll value, weight, amt; cin >> value >> weight >> amt; v_temp.push_back(value); c_temp.push_back(weight); t_temp.push_back(amt); } vi v, c, t; for (ll i = 0; i < n; i++) { ll totalWeight = (myMap[c_temp[i]] + t_temp[i]) * c_temp[i]; if (totalWeight > x) continue; myMap[c_temp[i]] += t_temp[i]; v.push_back(v_temp[i]); c.push_back(c_temp[i]); t.push_back(t_temp[i]); } n = v.size(); if (n == 0) { cout << 0; return; } for (ll i = 0; i < n; i++) { new_t.push_back(min(t[i], x / c[i])); } vector<vi> dp(n + 1, vi(x + 1, 0)); for (ll i = n - 1; i >= 0; i--) { for (ll j = 0; j <= x; j++) { dp[i][j] = dp[i + 1][j]; for (ll k = 1; k <= new_t[i]; k++) { if (j >= k * c[i]) { dp[i][j] = max(dp[i][j], k * v[i] + dp[i + 1][j - k * c[i]]); } } } } cout << dp[0][x]; } int main() { fast_io; 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...