Submission #724040

#	Time	Username	Problem	Language	Result	Execution time	Memory
724040		ivaziva	Knapsack (NOI18_knapsack)	C++14	0 / 100	1 ms	468 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

#define MAXN 100010
#define MAXM 2010

long long n;
long long s;
vector<priority_queue<pair<long long,long long>>> niz;
vector<pair<long long,pair<long long,long long>>> pomoc;
long long dp[MAXM];

int main()
{
    ios_base::sync_with_stdio(false);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>s>>n;
    for (long long i=1;i<=n;i++)
    {
        long long x,y,z;
        cin>>x>>y>>z;
        niz[y].push({x,z});
    }
    for (long long i=1;i<=s;i++)
    {
        long long ans=s/i;
        while (ans and niz[i].empty()==false)
        {
            pair<long long,long long> p=niz[i].top();
            niz[i].pop();
            long long v=p.first;
            long long k=p.second;
            for (long long j=1;j<=min(ans,k);j++) pomoc.push_back({v,{i,k}});
            ans-=min(ans,k);
        }
    }
    for (long long i=1;i<=s;i++)
    {
        dp[i]=dp[i-1];
        for (long long j=0;j<(long long)pomoc.size();j++)
        {
            if (i>=pomoc[j].second.first) dp[i]=max(dp[i],dp[i-pomoc[j].second.first]+pomoc[j].first);
        }
    }
    long long sol=0;
    for (long long i=1;i<=s;i++) sol=max(sol,dp[i]);
    cout<<sol<<endl;
}

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