Submission #1192956

#TimeUsernameProblemLanguageResultExecution timeMemory
1192956euclidKnapsack (NOI18_knapsack)C++20
49 / 100
24 ms32328 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]; vi 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++) { if(weight[w[i]].size() == 2000) continue; for(int j = 1; j <= min(k[i], (ll)2000-(ll)weight[w[i]].size()); j++) weight[w[i]].pb(v[i]); } // cout << weight[15].size() << '\n'; // cout << weight[1].size() << '\n'; for(int i = 1; i < MS; i++) { assert(weight[i].size() <= 2000); sort(weight[i].begin(), weight[i].end(), greater<>()); for(int j = 0; j < weight[i].size(); j++) { pref[i][j] = weight[i][j]; if(j != 0) pref[i][j] += pref[i][j-1]; } } 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]); for(int x = 1; x*i <= j && x <= weight[i].size(); x++) { dp[i][j] = max(dp[i][j], dp[i-1][j-x*i]+pref[i][x-1]); } } } cout << dp[MS-1][s] << '\n'; // 20 3 // 5000 15 1 // 100 1 3 // 50 1 4 }
#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...