Submission #399058

#	Time	Username	Problem	Language	Result	Execution time	Memory
399058		ak2006	Knapsack (NOI18_knapsack)	C++14	100 / 100	497 ms	258432 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
const ll mod = 1e9 + 7;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

map<int,vvl>vals;

int main()
{
    int s,n;
    cin>>s>>n;
    vvl a(n,vl(3));
    for (int i = 0;i<n;i++){cin>>a[i][0]>>a[i][1]>>a[i][2];vals[a[i][1]].push_back(a[i]);}

    if (n == 1){
        int weight = a[0][1],worth = a[0][0],copies = a[0][2];
        int num = s / weight;
        num = min(num,copies);
        cout<<worth * num;
        return 0;
    }

    vvl sack;

    for (int w = 1;w<=s;w++){
        vvl cur = vals[w];
        sort(cur.rbegin(),cur.rend());
        int num = s/w;
        int i = 0;
        while (i<(int)cur.size() && num > 0){
            num--;
            sack.push_back({cur[i][0],w});
            cur[i][2]--;
            if (cur[i][2] == 0)i++;
        }
    }

    n = (int)sack.size();
    vvl dp(n,vl(s + 1));

    for (int i = 0;i<n;i++){
        for (int j = 1;j<=s;j++){
            if (i != 0)dp[i][j] = dp[i - 1][j];
            if (j < sack[i][1])continue;
            int extra = (i == 0 ? 0 : dp[i - 1][j - sack[i][1]]);
            dp[i][j] = max(dp[i][j],sack[i][0] + extra);
        }
    }

    cout<<dp[n - 1][s];
    return 0;
}

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