Submission #1310290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310290		26rfeng	Knapsack (NOI18_knapsack)	C++20	37 / 100	3 ms	2776 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

int main() {
	int S, N; cin >> S >> N;
    long long V[100002], W[100002], K[100002];
    for (int i = 0; i < N; i++){
        cin >> V[i] >> W[i] >> K[i];
    }
    long long dp[2][2002];
    for (int i = 0; i < 2002; i++){
        dp[0][i] = -1;
        dp[1][i] = -1;
    }
    int curr = 0, next = 1;
    for (int i = 0; i <= K[0]; i++){
        dp[curr][i*W[0]] = i*V[0];
    }
    for (int i = 0; i < N-1; i++){
        curr = i%2; next = (i+1)%2;
        for (int s = 0; s <= S; s++){
            if (dp[curr][s] == -1){
                // cout << i << " " << s << " " << dp[curr][s] << endl;
                continue;
            }
            for (int k = 0; k <= K[i+1]; k++){
                if (s+k*W[i+1] > S) break;
                dp[next][s+k*W[i+1]] = max(dp[curr][s] + k*V[i+1], dp[next][s+k*W[i+1]]);
            }
            // cout << i << " " << s << " " << dp[curr][s] << endl;
        }
    }

    long long ans = 0;
    for (int i = 0; i <= S; i++){
        ans = max(ans, dp[(N-1)%2][i]);
    }
    cout << ans << endl;
}

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