Submission #700211

#	Time	Username	Problem	Language	Result	Execution time	Memory
700211		mariacichosz	Knapsack (NOI18_knapsack)	C++17	100 / 100	62 ms	3708 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);
        // cout << i << ":\n";
        for (int j = s; j >= 0; j --){
            // cout << 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);
                // cout << j + ile * i << ": " << dp[j + ile * i] << "\n";
                ile ++; ilei ++;
            }
        }
    }
    // for (int i = 0; i < n; i ++){
    //     int v = value[i], w = weight[i], a = amount[i];
    //     for (int j = s - w; j >= 0; j --){
    //         for (int k = 1; k <= min(a, (s - j) / w); k ++){
    //             dp[j + k * w] = max(dp[j + k * w], dp[j] + k * v);
    //         }
    //     }
    // }
    // int ans = 0;
    // for (int i = 0; i <= s; i ++) ans = max(ans, dp[i]);
    // cout << ans << "\n";
    cout << dp[s] << "\n";
}

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