Submission #743573

#	Time	Username	Problem	Language	Result	Execution time	Memory
743573		LKR__enjoyer	Knapsack (NOI18_knapsack)	C++17	100 / 100	227 ms	4892 KiB

knapsack

#include<bits/stdc++.h>
#include <iostream>
typedef long long ll;
#define pb push_back
#define f first
#define s second
using namespace std;
ll dp[2001];
priority_queue<pair<ll,int>> kolejka[2001];
int n,max_weight;
void put(int waga){
auto x=kolejka[waga].top(); 
kolejka[waga].pop();
ll val=x.f; x.s--;
if(x.s)kolejka[waga].push(x);
if(kolejka[waga].top().s==0)kolejka[waga].pop();    
for(int i=max_weight-waga;i>=0;i--)
dp[i+waga]=max(dp[i+waga],dp[i]+val);
for(int i=1;i<=max_weight;i++)dp[i]=max(dp[i],dp[i-1]);    
}


int main()
{
    cin>>max_weight>>n;
    for(int i=0;i<n;i++){
    ll v; int w,k;    
    cin>>v>>w>>k;    
    kolejka[w].push({v,k});
    }
    for(int i=1;i<=max_weight;i++){
    for(int j=0;j<max_weight/i;j++){
    if(kolejka[i].empty())break;
    put(i);
    }    
    }
    cout<<dp[max_weight];
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27