Submission #876406

#	Time	Username	Problem	Language	Result	Execution time	Memory
876406		arkash707	Knapsack (NOI18_knapsack)	C++17	0 / 100	1038 ms	1212 KiB

knapsack

#include<iostream>
#include<vector>
using namespace std;

int s, n;

//good: {price, weight, quantity}
int a[100001][3];

int solve() {

    int dp[n+1][s+1];
    for (int i=0; i<n; i++) {
        for (int j=0; j<=s; j++) dp[i][j] = 0;
    }


    int res = 0;
    for (int i=0; i<n; i++) {
        int price = a[i][0], weight = a[i][1], quantity = a[i][2];
        for (int j=s; j>=0; j--) {
            int maxPrice = price*quantity;
            int maxWeight = weight*quantity;
            for (int k=quantity; k>0; k--, maxWeight-=weight, maxPrice-=price) {
                if (j-maxWeight < 0 || (dp[i][j-maxWeight] == 0 && j-maxWeight != 0)) continue;
                dp[i][j] = max(dp[i][j], dp[i][j-maxWeight] + maxPrice);
                dp[i+1][j] = dp[i][j];
                res = max(res, dp[i][j]);

            }
        }
    }


    // for (int i=0; i<n; i++) {
    //     for (int j=0; j<=s; j++) cout << dp[i][j] << " ";
    //     cout << "\n";
    // }


    return res;



}



int main() {
	
    // #ifndef ONLINE_JUDGE
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	// #endif

    cin >> s >> n;
    for (int i=0; i<n; i++) {
        for (int j=0; j<3; j++) {
            cin >> a[i][j];
        }
    }
    cout << solve() << "\n";
}

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