Submission #675995

#	Time	Username	Problem	Language	Result	Execution time	Memory
675995		Ozy	Knapsack (NOI18_knapsack)	C++17	100 / 100	58 ms	4996 KiB

knapsack

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define lli long long int
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pb push_back

#define MAX 2000
#define valor first
#define cant second

lli s,n,a,b,c,umbral,contador;
vector<pair<lli,lli> > peso[MAX+2];
lli dp[MAX+2];

void solve(lli dis, lli costo) {
    repa(i,s,dis) {
        dp[i] = max(dp[i], dp[i-dis] + costo);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> s >> n;
    rep(i,1,n) {
        cin >> a >> b >> c;
        peso[b].pb({a,c});
    }

    rep (i,1,s) {
        if (peso[i].empty()) continue;

        sort(peso[i].begin(), peso[i].end());
        reverse(peso[i].begin(), peso[i].end());
        umbral = s/i;
        contador = 0;

        for (auto act : peso[i]) {
            rep(j,1,act.cant) {
                contador++;
                if (contador > umbral) break;

                solve(i,act.valor);
            }
            if (contador > umbral) break;
        }

    }

    cout << dp[s];
}

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