Submission #1178591

#TimeUsernameProblemLanguageResultExecution timeMemory
1178591HezovKnapsack (NOI18_knapsack)C++20
0 / 100
1 ms576 KiB
#include <iostream> #include <algorithm> #include <vector> using namespace std; struct item{int val, cnt;}; vector<item> A[2002]; int dp[101][101]; // dp[i][j] - considerand greutati pana la i care e // valoarea maxima obtinuta cu capacitatea j. bool cmp(item a, item b) { return a.val > b.val; } int main() { int S, N; cin >> S >> N; for(int i = 1;i<=N;i++) { int v, w, k; cin >> v >> w >> k; A[w].push_back({v,k}); } for(int i = 1;i<=S;i++) if(!A[i].empty()) sort(A[i].begin(),A[i].end(),cmp); for(int i = 1;i<=S;i++) // consideram greutatea i { // Avem un rucsac cu capacitatea G for(int G = 1;G<=S;G++) { int sumV = 0, taken = 0 ; dp[i][G] = dp[i-1][G]; for(int j = 0; j < A[i].size();j++) { // Ne aflam intr-un item si nu stim cate sa luam din el. if(taken + 1 > G / i) break; for(int it = 1; it <= A[i][j].cnt;it++) { if(taken + 1 > G / i) break; taken++; sumV += A[i][j].val; dp[i][G] = max(dp[i][G], dp[i - 1][G - taken * i] + sumV); } } } } cout << dp[S][S] << '\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...