제출 #753859

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
753859		ivaziva	Knapsack (NOI18_knapsack)	C++14	73 / 100	363 ms	262144 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

#define MAXN 100010
#define MAXM 2010

//sutra ujutru kucam ovo

long long s;
long long n;
long long w[MAXN];
long long v[MAXN];
long long k[MAXN];
vector<pair<long long,long long>> vec;
long long dp[MAXM];

int main()
{
    cin>>s>>n;
    for (long long i=1;i<=n;i++) cin>>v[i]>>w[i]>>k[i];
    for (long long i=1;i<=n;i++)
    {
        long long br=min(s/w[i],k[i]);
        for (long long j=1;j<=br;j++) vec.push_back({w[i],v[i]});
    }
    long long siz=vec.size();
    sort(vec.begin(),vec.end());
    long long ans=0;
    for (long long i=0;i<siz;i++)
    {
        long long ww=vec[i].first;
        long long vv=vec[i].second;
        for (long long j=ww;j<=s;j++)
        {
            dp[j-ww]=max(dp[j-ww],dp[j]+vv);
            ans=max(ans,dp[j-ww]);
        }
    }
    cout<<ans<<endl;
}

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