Submission #635829

#TimeUsernameProblemLanguageResultExecution timeMemory
635829zeroesandonesKnapsack (NOI18_knapsack)C++17
37 / 100
1086 ms66032 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef long double ld; typedef vector<ll> vi; typedef pair<ll, ll> pi; #define FOR(i, j, k) for (ll i = j; i < (ll) k; ++i) #define FORD(i, j, k) for (ll i = j; i >= (ll) k; --i) #define nl "\n" #define all(x) (x).begin(), (x).end() #define sc second #define fr first #define pb push_back void solve() { int s, n; cin >> s >> n; vector<pi> a; FOR(i, 0, n) { int v, w, k; cin >> v >> w >> k; FOR(j, 0, k) { a.pb({v, w}); } } ll dp[s + 1] = {}; FOR(i, 0, a.size()) { FORD(j, s, 1) { if(j - a[i].sc >= 0) { dp[j] = max(dp[j], dp[j - a[i].sc] + a[i].fr); } } } cout << dp[s] << nl; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll t = 1; // cin >> t; while (t--) { solve(); } }
#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...