Submission #843882

#	Time	Username	Problem	Language	Result	Execution time	Memory
843882		Ablabla	Knapsack (NOI18_knapsack)	C++11	0 / 100	161 ms	348 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

int s, n;
map<int, vector<pii>> sorban;
vector<vector<int>> dp;
vector<int> indexek;

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

    int vissza = 0;
    int plusz = 0;
    int minusz = 0;

    for(int i = 0; i < (int)sorban[indexek[ind]].size(); i++){
        for(int j = 0; j < sorban[indexek[ind]][i].second; j++){
            minusz += indexek[ind] + 1;
            plusz += sorban[indexek[ind]][i].first;
            int a = (maradt - minusz >= 0 ? megold(ind + 1, maradt - minusz) + plusz : 0);

            //cout << ind << " " << maradt << " : " << a << " : " << plusz << " " << minusz << "\n";

            vissza = max(vissza, a);
        }
    }

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

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


    for(int i = 0; i < n; i++){
        int ertek, suly, db;
        cin >> ertek >> suly >> db;

        if(sorban[suly - 1].size() == 0){
            indexek.push_back(suly - 1);
        }
        sorban[suly - 1].push_back({ertek, db});
    }

    sort(indexek.begin(), indexek.end());
    dp.assign(sorban.size(), vector<int>(s + 1, -1));

    for(auto &x : sorban){
        sort(x.second.begin(), x.second.end(), greater<pii>());
    }

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

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