Submission #668292

#	Time	Username	Problem	Language	Result	Execution time	Memory
668292		_martynas	Knapsack (NOI18_knapsack)	C++11	100 / 100	58 ms	9548 KiB

knapsack

#include <bits/stdc++.h>

#define F first
#define S second
#define PB push_back

using namespace std;

using ll = long long;

void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

const int MXN = 1e5+5;

int s, n;
ll W[MXN], V[MXN], K[MXN];
ll dp[MXN];
vector<pair<ll, ll>> best[MXN];

int main() {
    FASTIO();

    cin >> s >> n;
    for(int i = 0; i < n; i++) {
        cin >> V[i] >> W[i] >> K[i];
        K[i] = min(K[i], (ll)s);
        best[W[i]].PB({V[i], K[i]});
    }

    for(int i = 1; i <= s; i++) {
        sort(best[i].rbegin(), best[i].rend());
        int k = 0;
        for(auto p : best[i]) {
            for(int j = 0; j < p.S; j++) {
                if(i*k > s) break;
                for(int u = s; u >= i; u--) {
                    dp[u] = max(dp[u], dp[u-i]+p.F);
                }
                k++;
            }
        }
    }

    cout << *max_element(dp, dp+s+1) << "\n";

    return 0;
}

/*



*/

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