제출 #887710

#제출 시각아이디문제언어결과실행 시간메모리
887710votranngocvyKnapsack (NOI18_knapsack)C++14
100 / 100
70 ms34388 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fi first #define se second #define mp make_pair const int N = 1e5 + 5; int dp[2005][2005]; vector<pii>a[2005]; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,s; cin >> s >> n; for (int i = 1; i <= n; i++) { int v,w,k; cin >> v >> w >> k; a[w].push_back(mp(v,k)); } for (int i = 1; i <= 2000; i++) sort(a[i].begin(),a[i].end(),greater<pii>()); int ans = 0; for (int i = 1; i <= 2000; i++) { for (int j = 0; j <= s; j++) { dp[i][j] = max(dp[i][j],dp[i - 1][j]); int sumW = 0,sumV = 0; for (auto x: a[i]) { for (int k = 1; k <= x.se; k++) { sumW += i,sumV += x.fi; if (sumW > j) break; dp[i][j] = max(dp[i][j],dp[i - 1][j - sumW] + sumV); } if (sumW > j) break; } ans = max(ans,dp[i][j]); } } cout << ans << "\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...