Submission #700212

#	Time	Username	Problem	Language	Result	Execution time	Memory
700212		mariacichosz	Knapsack (NOI18_knapsack)	C++17	100 / 100	63 ms	1880 KiB

knapsack

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

#define ll long long
#define pb push_back
#define st first
#define nd second
#define sz size

const int N = 1e5 + 5;
const int S = 2005;

int dp[S];
vector <pair<int, int>> val_amt[S];

bool cmp(pair<int, int> a, pair<int, int> b){
    if (a.st > b.st) return 1;
    return 0;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, s;
    cin >> s >> n;
    for (int i = 0; i < n; i ++) {
        int v, w, a;
        cin >> v >> w >> a;
        val_amt[w].pb({v, a});
    }
    for (int i = 1; i <= s; i ++){
        if (val_amt[i].empty()) continue;
        sort(val_amt[i].begin(), val_amt[i].end(), cmp);
        for (int j = s; j >= 0; j --){
            int ile = 1, ind = 0, ilei = 1;
            int v = 0;
            while(j + ile * i <= s && ind < (int)val_amt[i].sz()){
                if (ilei > val_amt[i][ind].nd){
                    ind ++;
                    ilei = 1;
                    continue;
                }
                v += val_amt[i][ind].st;
                dp[j + ile * i] = max(dp[j + ile * i], dp[j] + v);
                ile ++; ilei ++;
            }
        }
    }
    cout << dp[s] << "\n";
}

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