Submission #675427

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
6754272022-12-27 08:58:29ToxtaqKnapsack (NOI18_knapsack)C++17
37 / 100
132 ms262144 KiB
#include <bits/stdc++.h>
using namespace std;
int main()
{
int S, n;
cin >> S >> n;
vector<pair<int, int> >items;
items.push_back({0, 0});
for(int i = 0;i < n;++i){
int v, w, k;
cin >> v >> w >> k;
for(int j = 0;j < k;++j){
items.push_back({w, v});
}
}
n = items.size();
int Max = 0;
vector<vector<int> >dp(n, vector<int>(S + 1, -1e9));
dp[0][0] = 0;
for(int i = 1;i < n;++i){
for(int j = S;j >= 0;--j){
if(j - items[i].first >= 0)dp[i][j] = max(dp[i][j], dp[i - 1][j - items[i].first] + items[i].second);
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
Max = max(Max, dp[i][j]);
}
}
cout << Max;
}
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#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...