제출 #1059398

#제출 시각아이디문제언어결과실행 시간메모리
1059398theehannKnapsack (NOI18_knapsack)C++17
12 / 100
0 ms348 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ft first #define se second #define NAME "A" #define file freopen(NAME".INP","r",stdin); freopen(NAME".OUT","w",stdout); #define sdf ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define el cout << "\n" const int MOD = 1e9 + 7, N = 1e5 + 5; int n, S; int32_t main(){ sdf cin >> S >> n; map<int, vector<pair<int, int>>> by_weight; for(int i = 1;i <= n;++i){ int v, w, k; cin >> v >> w >> k; by_weight[w].push_back({v, k}); } int in = 1, ans = 0 ; vector<vector<int>> dp(by_weight.size() + 2, vector<int>(S, -1e17)); dp[0][0] = 0; for(auto &[w, a] : by_weight){ sort(a.begin(), a.end(), greater<pair<int, int>>()); for(int j = 0;j <= S;++j){ dp[in][j] = dp[in-1][j]; int c = 0, cur = 0; unsigned int id = 0; while((c + 1) * w <= j && id < a.size()){ cur += a[id].ft; c++; dp[in][j] = max(dp[in][j], dp[in-1][j-c*w] + cur); ans = max(ans, dp[in][j]); if(c == a[id].se){ c = 0; id++; } } } in++; } cout << ans; 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...