Submission #945316

#	Time	Username	Problem	Language	Result	Execution time	Memory
945316		mariamp1	Knapsack (NOI18_knapsack)	C++14	100 / 100	139 ms	125412 KiB

knapsack

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
const int N = 2000 + 5;
vector<pair<int, int> > vec[N], nw;
int dp[2000 * 15][N];
int main(){
    int s, n; cin >> s >> n;
    int val, w, r;
    for(int i = 1; i <= n; i++){
        cin>>val>>w>>r;
        vec[w].push_back({val, r});
    }

    for(int i = 1; i <= s; i++){
        sort(vec[i].begin(), vec[i].end());
        reverse(vec[i].begin(), vec[i].end());
        int tot = s / i;
        for(int j = 0; j < (int)vec[i].size(); j++){
            int raod = vec[i][j].second;
            int value = vec[i][j].first;
            if (raod <= tot){
                for(int z = 1; z <= raod; z++){
                    nw.push_back({i, value});
                }
                tot -= raod;
            } else {
                for(int z = 1; z <= tot; z++){
                    nw.push_back({i, value});
                }
                tot = 0;
                break;
            }
        }
    }
    // dp[i][j]    pirveli i cali nivti, j aris wona = maximaluri value
    n = nw.size();
    int ans = 0;
    for(int i = 1; i <= n; i++){
        int wona = nw[i - 1].first;
        int value = nw[i - 1].second;
        for(int j = 0; j <= s; j++){
            dp[i][j] = dp[i-1][j];
            if (j >= wona) dp[i][j] = max(dp[i][j], dp[i-1][j-wona]+value);
            ans = max(ans, dp[i][j]);
        }
    }
    cout<<ans<<endl;
}

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