제출 #1096548

#제출 시각아이디문제언어결과실행 시간메모리
1096548IrateKnapsack (NOI18_knapsack)C++17
100 / 100
41 ms3820 KiB
#include<bits/stdc++.h> using namespace std; const int MAX = 2005; struct Item{ int v, w, k; bool operator<(Item &other){ if(w == other.w)return v > other.v; return w < other.w; } }; vector<long long>dp1, dp2; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); dp1.assign(MAX, -1e18); dp2.assign(MAX, -1e18); dp2[0] = 0; int n, S; cin >> S >> n; vector<Item>vv(n); for(int i = 0;i < n;++i){ int v, w, k; cin >> v >> w >> k; vv[i] = {v, w, k}; } sort(vv.begin(), vv.end()); vector<vector<int>>items(S + 1); for(int i = 0;i < n;++i){ int v = vv[i].v, w = vv[i].w, k = vv[i].k; for(int j = 0;j < min(k, S / w) && (int)items[w].size() + 1 <= S / w;++j){ items[w].push_back(v); } } for(int i = 1;i <= S;++i){ for(int j = 0;j <= S;++j){ long long sum = 0; dp1[j] = dp2[j]; for(int k = 0;k < (int)items[i].size() && j - (k + 1) * i >= 0;++k){ sum += items[i][k]; dp1[j] = max(dp1[j], dp2[j - (k + 1) * i] + sum); } } dp2 = dp1; } long long mx = 0; for(int i = 1;i <= S;++i){ mx = max(mx, dp1[i]); } cout << mx << '\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...