Submission #446066

#	Time	Username	Problem	Language	Result	Execution time	Memory
446066		MaisyDoge13	Knapsack (NOI18_knapsack)	C++17	100 / 100	154 ms	5024 KiB

knapsack

#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <cmath>
#include <algorithm>
#include <array>
#include <set>
#include <climits>
#include <map>
#include <memory>
#include <string>
#include <deque>
#include <queue>
#include <stack>
using namespace std;

#define input "knapsack.in"
#define output "knapsack.out"
#define int long long
typedef pair<int, int> pii;
int S, n;
vector<vector<pii>> items;//grouped by weight
vector<pii> all_items;//each weight can have up to S pounds in this vector, making it SlogS
vector<int> dp;//for each weight, what is the maximum value possible?
int res=0;
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen(input, "r", stdin);
    //freopen(output, "w", stdout);
    cin >> S >> n;
    items.resize(S+1);
    dp.resize(S+1, 0);
    for (int i=0;i<n;i++) {
        int val, wt, amt;
        cin >> val >> wt >> amt;
        items[wt].push_back({val, amt});
    }
    for (int s=1;s<=S;s++) {
        sort(items[s].begin(), items[s].end(), [](pii& a, pii& b) -> bool {
            return a.first>b.first;
        });
    }
    all_items.reserve(S*S);
    for (int s=1;s<=S;s++) {
        int curr_weight=0;
        for (pii item: items[s]) {
            for (int k=0;k<item.second;k++) {
                curr_weight+=s;
                if (curr_weight>S) break;
                all_items.push_back({s, item.first});
            }
            if (curr_weight>S) break;
        }
    }
    for (pii item: all_items) {
        //out << item.first << ' ' << item.second << endl;
        for (int s=S-1;s>=0;s--) {
            if (item.first+s>S) continue;
            dp[item.first+s]=max(dp[item.first+s], item.second+dp[s]);
            res=max(res, dp[item.first+s]);
        }
    }
    //for (int s=0;s<=S;s++) cout << dp[s] << ' '; cout << endl;
    //cout << all_items.size() << endl;
    cout << res << endl;
}

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