Submission #1131028

#TimeUsernameProblemLanguageResultExecution timeMemory
1131028Braabebo10Knapsack (NOI18_knapsack)C++20
100 / 100
366 ms66784 KiB
#include<bits/stdc++.h> #define ll long long #define nl "\n" #define all(v) v.begin(),v.end() #define baraa ios_base::sync_with_stdio(false);cin.tie(NULL); using namespace std; int main() { baraa ll s, n, m = 2e3 + 5; cin >> s >> n; vector<vector<ll>>w(m); vector<array<ll, 3>>a(n); for (ll i = 0; i < n; i++) for(ll j = 0; j < 3; j++) cin >> a[i][j]; sort(all(a), greater()); for (ll i = 0; i < n; i++) while(w[a[i][1]].size() < m and a[i][2]--) w[a[i][1]].push_back(a[i][0]); vector<vector<ll>>dp(m, vector<ll>(m, -1)); function<ll(ll, ll)>solve = [&](ll i, ll rem) -> ll{ if (rem < 0)return -1e16; if (i == m)return 0; if (dp[i][rem] != -1)return dp[i][rem]; ll ret = solve(i + 1, rem), prf = 0, cost = 0; for (ll j = 0; j < w[i].size() and rem - cost + i >= 0; j++){ prf += w[i][j]; cost += i; ret = max(ret, solve(i + 1, rem - cost) + prf); } return dp[i][rem] = ret; }; cout << solve(0, s); 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...