# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1065981 | KALARRY | Knapsack (NOI18_knapsack) | C++14 | 46 ms | 3676 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//chockolateman
#include<bits/stdc++.h>
using namespace std;
int N,S,dp[2005]; //max val with space i
vector<pair<int,int>> items[2005];
int main()
{
scanf("%d%d",&S,&N);
for(int v,w,k,i = 1 ; i <= N ; i++)
{
scanf("%d%d%d",&v,&w,&k);
items[w].push_back({v,k});
}
for(int i = 1 ; i <= S ; i++)
{
sort(items[i].begin(),items[i].end(),greater<pair<int,int>>());
int space_taking = 0;
for(auto e : items[i])
{
int v = e.first;
int w = i;
int k = e.second;
for(int x = 1 ; space_taking <= S && x <= k ; x++)
{
space_taking += w;
if(space_taking <= S)
{
for(int j = S ; j >= w ; j--)
dp[j] = max(dp[j],dp[j-w] + v);
}
}
}
}
printf("%d\n",dp[S]);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |