제출 #1310288

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310288		26rfeng	Knapsack (NOI18_knapsack)	C++20	0 / 100	3 ms	2700 KiB

knapsack

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

int main() {
	int S, N; cin >> S >> N;
    long long V[100001], W[100001], K[100001];
    for (int i = 0; i < N; i++){
        cin >> V[i] >> W[i] >> K[i];
    }
    long long dp[2][2000];
    for (int i = 0; i < 2000; 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; 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++){
                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: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27