# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
500798 | pancankes | Knapsack (NOI18_knapsack) | C++17 | 0 ms | 0 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.
#include <iostream>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define ll long long
const int MAXN=1e5+2;
const int MOD=1e9+7;
int main()
{
ll s,n;
cin >> s >> n;
// since s<=2000, and n<=1000000
// there will inevitably be repeated weights, so we can group them together
map<int, vector<pair<int,int> > >weights;
for (int i=0; i<n; i++)
{
int p,w,n;
cin >> p >> w >> n;
weights[w].push_back({p,n});
}
vector<vector<int>> dp(weights.size()+1,vector<int>(s+1,0));
dp[0][0]=0;
int at=1;
for (auto& [w, items] : weights)
{
sort(items.rbegin(),items.rend());
for (int i=0; i<=s; i++)