제출 #766530

#제출 시각아이디문제언어결과실행 시간메모리
766530MathandskiKnapsack (NOI18_knapsack)C++14
12 / 100
1 ms212 KiB
#define pb push_back #define mt make_tuple #define mp make_pair #define is insert #define ll int #define vl vector<ll> #define sl set<ll> #define msl multiset<ll> #define pl pair<ll, ll> #define vpl vector<pair<ll, ll>> #define f0r(i, begin, end) for (ll i = begin; i < end; i ++) #define len(x) x.size() #include "bits/stdc++.h" using namespace std; struct item { int value, weight, amount; }; bool comp (item a, item b) { return (a.value * b.weight) > (b.value * a.weight); } vector<item> items; bool visited[2001]; int dp[2001], S, N, ans = 0; int main () { ios_base::sync_with_stdio(0); cin.tie(nullptr); cin >> S >> N; f0r (i, 0, N) { int a, b, c; cin >> a >> b >> c; items.pb({a, b, c}); } sort(items.begin(), items.end(), comp); visited[0] = 1; for (auto i : items) { f0r (j, 0, i.amount) { bool updated = false; for (int k = S; k >= i.weight; k --) { if(visited[k - i.weight] && (!visited[k])) { updated = true; visited[k] = 1; dp[k] = dp[k - i.weight] + i.value; ans = max(ans, dp[k]); } } if(!updated) break; } } cout << ans << 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...