Submission #1303194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303194		trungcan	Knapsack (NOI18_knapsack)	C++17	100 / 100	38 ms	1780 KiB

knapsack

#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second

using namespace std;

const int N = 2005, INF = 2e9 + 7;

int S, n, dp[N], ans = 0;
vector<pii> lis[N];

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

    cin >> S >> n;
    for (int i = 1, v, w, k; i <= n; ++i){
        cin >> v >> w >> k;
        lis[w].push_back({v, k});
    }

    for (int i = 1; i <= S; ++i) dp[i] = -INF;
    dp[0] = 0;

    for (int i = 1; i <= S; ++i){
        sort(lis[i].begin(), lis[i].end(), greater<pii>());

        int total = 0;
        for (pii x: lis[i]){
            for (int j = 1; j <= x.se; ++j, total += i){
                if (total > S) break;
                for (int k = S; k >= i; --k)
                    dp[k] = max(dp[k], dp[k - i] + x.fi);
            }
            if (total > S) break;
        }
    }

    for (int i = S; i >= 0; --i) ans = max(ans, dp[i]);

    cout << ans;
}

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