Submission #985773

#	Time	Username	Problem	Language	Result	Execution time	Memory
985773		lftroq	Knapsack (NOI18_knapsack)	C++14	100 / 100	61 ms	35120 KiB

knapsack

#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
#define fi first
#define se second
using namespace std;
typedef long long ll;

const int INF=1e9;

ll dp[2001][2001];

void solve()
{
    int s,n;
    cin >> s >> n;
    map<int,vector<pair<int,int>>> bw;
    for(int i=0;i<n;i++)
    {
        int v,w,k;
        cin >> v >> w >> k;
        if(w<=s&&k) bw[w].push_back({v,k});
    }
    for(int i=0;i<=(int)bw.size();i++) for(int j=0;j<=s;j++) dp[i][j]=-INF;
    dp[0][0]=0;
    int p=0;
    for(map<int,vector<pair<int,int>>>::iterator it=bw.begin();it!=bw.end();it++)
    {
        p++;
        int w=it->fi;
        vector<pair<int,int>> temp=it->se;
        sort(temp.begin(),temp.end(),greater<pair<int,int>>());
        for(int i=0;i<=s;i++)
        {
            dp[p][i]=dp[p-1][i];
            int c=0,t=0,cr=0;
            ll pr=0;
            while((c+1)*w<=i&&t<(int)temp.size())
            {
                c++;
                pr+=temp[t].fi;
                if(dp[p-1][i-c*w]!=-INF) dp[p][i]=max(dp[p][i],dp[p-1][i-c*w]+pr);
                cr++;
                if(cr==temp[t].se)
                {
                    cr=0;
                    t++;
                }
            }
        }
    }
    ll ans=-1e16;
    for(int i=0;i<=s;i++) ans=max(ans,dp[p][i]);
    cout << ans << endl;
}

int main()
{
    fastIO
    solve();
    return 0;
}

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