제출 #843648

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
843648		Ablabla	Knapsack (NOI18_knapsack)	C++11	73 / 100	562 ms	262144 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

struct termek{
    int ertek;
    int suly;
    int mennyiseg;
};

int s, n;
vector<vector<int>> dp;
vector<termek> termekek;

int megold(int ind, int maradt){
    if(maradt < 0){
        return 0;
    }
    if(ind == n){
        return 0;
    }
    if(dp[ind][maradt] != -1){
        return dp[ind][maradt];
    }

    int vissza = 0;

    for(int i = 0; i <= termekek[ind].mennyiseg && maradt - termekek[ind].suly * i >= 0; i++){
        int a = megold(ind + 1, maradt - termekek[ind].suly * i) + termekek[ind].ertek * i;
        //cout << ind << " : " << i << " : " << a << "\n";

        vissza = max(vissza, a);
    }

    return dp[ind][maradt] = vissza;
}

int main()
{
    cin >> s >> n;

    dp.assign(n, vector<int>(s + 1, -1));
    termekek.assign(n, {0, 0, 0});

    for(int i = 0; i < n; i++){
        int a, b, c;
        cin >> a >> b >> c;

        termekek[i] = {a, b, c};
    }

    cout << megold(0, s) << "\n";
}

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