Submission #668043

#	Time	Username	Problem	Language	Result	Execution time	Memory
668043		_martynas	Knapsack (NOI18_knapsack)	C++11	73 / 100	1090 ms	3860 KiB

knapsack

#include <bits/stdc++.h>

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];

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);
    }

    dp[0] = 0;
    for(int i = 0; i < n; i++) {
        int w = W[i], v = V[i];
        for(int k = 0; k < 11; k++) {
            if(!K[i]) break;
            int iterations = (K[i] & (1 << k) ? 1 : 2);
            for(int c = 0; c < iterations; c++) {
                for(int j = s; j >= w; j--) {
                    dp[j] = max(dp[j], dp[j-w]+v);
                }
                K[i] -= 1 << k;
            }
            w *= 2;
            v *= 2;
        }
    }
    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: 0 / 27