Submission #1014749

#TimeUsernameProblemLanguageResultExecution timeMemory
1014749MackerKnapsack (NOI18_knapsack)C++17
29 / 100
2 ms440 KiB
#include <bits/stdc++.h> using namespace std; typedef long double ld; typedef long long ll; #define int ll typedef pair<int, int> pii; #define all(v) v.begin(), v.end() #define FOR(i, n) for (int i = 0; i < n; i++) #define inf LLONG_MAX/2 #define ff first #define ss second #define ckmin(a, b) a = min(a, b) #define ckmax(a, b) a = max(a, b) //#pragma GCC optimize("Ofast") //#pragma GCC target("avx2") signed main() { int x, n; cin >> x >> n; vector<vector<pii>> m(x + 1); FOR(i, n){ int v, w, k; cin >> v >> w >> k; m[w].push_back({k, v}); } FOR(i, x + 1) sort(all(m[i])); vector<int> dp(x + 1); for (int i = 1; i <= x; i++) { int sv = 0; int sw = 0; FOR(cnt, x / i + 1){ if(m[i].size() == 0) break; sw = i; sv = m[i].back().ss; m[i].back().ff--; if(m[i].back().ff == 0) m[i].pop_back(); for (int j = x; j >= 0; j--) { if(j + sw > x) continue; ckmax(dp[j + sw], dp[j] + sv); } } } cout << dp[x] << endl; }
#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...