Submission #1193037

#TimeUsernameProblemLanguageResultExecution timeMemory
1193037euclidKnapsack (NOI18_knapsack)C++20
100 / 100
81 ms68676 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define fi first #define se second #define vi vector<int> #define pii pair<int, int> #define pll pair<ll, ll> #define vl vector<ll> int n, s; const int MN = 1e5 + 3, MS = 2003; ll v[MN], w[MN], k[MN]; vector<pll> ww[MS]; vector<ll> weight[MS]; //weight[i] - all (up to 2000) items with weight i sorted in decreasing value ll dp[MS][MS], pref[MS][MS]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> s >> n; for(int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> k[i]; for(int i = 1; i <= n; i++) ww[w[i]].pb({v[i], k[i]}); for(int i = 1; i < MS; i++) { sort(ww[i].begin(), ww[i].end(), greater<>()); for(pll p : ww[i]) { if(weight[i].size() == 2001) break; ll sz = (ll) weight[i].size(); for(int j = 1; j <= min(2001-sz, p.se); j++) weight[i].pb(p.fi); } } for(int i = 1; i < MS; i++) { for(int j = 1; j <= s; j++) { dp[i][j] = max(dp[i][j], dp[i-1][j]); ll sum = 0; for(int x = 1; x*i <= j && x <= (int)weight[i].size(); x++) { sum += weight[i][x-1]; dp[i][j] = max(dp[i][j], dp[i-1][j-x*i]+sum); } } } cout << dp[MS-1][s] << '\n'; }
#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...