Submission #988664

#	Time	Username	Problem	Language	Result	Execution time	Memory
988664		lucascgar	Knapsack (NOI18_knapsack)	C++17	100 / 100	54 ms	21332 KiB

knapsack

#include <bits/stdc++.h>

// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

/*

N items, max basket S, worth Vi, weighs Wi, Ki copies (K<=1e9)

*/

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // overclock random

typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

const int MAXN = 1e5+10, MAXS = 2e3+10;

long long dp[MAXS], o[MAXS], v[MAXS][MAXS];
vector<pll> w[MAXS];

signed main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    // cout << fixed << setprecision(12);

    int s, n;
    cin >> s >> n;

    long long x, y, k;
    vector<int> it;
    for (int i=1;i<=n;i++){
        cin >> x >> y >> k;
        if (w[y].empty()) it.push_back(y);
        w[y].emplace_back(x, k);
    }

    for (auto x:it){
        sort(w[x].begin(), w[x].end());
        reverse(w[x].begin(), w[x].end());
        int l = x;
        for (auto i:w[x]){
            k = l + x*i.second-x;
            if (k>s) k = s;

            for (;l<=k;l+=x){
                v[x][l] = v[x][l-x]+i.first;
            }

        }

    }

    long long ans = 0;

    for (auto x:it){
        for (int i=0;i<=s;i++) o[i] = dp[i];

        for (int m=x;m<=s;m+=x){

            for (int i=s;i>=m;i--){
                dp[i] = max(dp[i], o[i-m]+v[x][m]);
                if (dp[i]>ans) ans = dp[i];
            }

        }

    }

    cout << ans << "\n";

    return 0;
}

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