Submission #967769

#	Time	Username	Problem	Language	Result	Execution time	Memory
967769		Gurban	Knapsack (NOI18_knapsack)	C++17	100 / 100	60 ms	3960 KiB

knapsack

    #include <bits/stdc++.h>
    using namespace std;
     
    using ll = long long;
     
    int s, mn;
     
    vector<ll> dp;
     
    vector<int> V, W;
     
    vector<vector<pair<int, int>>> u;
     
    int main() {
    	ios::sync_with_stdio(false); cin.tie(nullptr);
     
    	int S, n;
    	cin >> S >> n;
     
    	u.assign(S + 1, {});
    	while (n--) {
    		int v, w, k;
    		cin >> v >> w >> k;
     
    		u[w].push_back({v, k});
    	}
     
    	for (int i = 1; i <= S; i++) {
    		if (u[i].empty()) continue;
    		
    		sort(u[i].rbegin(), u[i].rend());
     
    		s = S / i;
    		for (auto j : u[i]) {
    			mn = min(s, j.second);
     			int now = mn;
    			while (mn--) {
    				V.push_back(j.first);
    				W.push_back(i);
    			}
     
    			s -= now;
     
    			if (!s) break;
    		}
    	}
     
    	// assert((int)V.size() <= 100000);
     
    	dp.assign(S + 1, -1);
    	dp[0] = 0;
    	for (int i = 0; i < (int)V.size(); i++) {
    		for (int j = S; j >= W[i]; j--)
    			if (j - W[i] >= 0 && j - W[i] <= S && dp[j - W[i]] != -1) dp[j] = max(dp[j], dp[j - W[i]] + V[i]);
    	}
     
    	ll mx = 0;
    	for (auto i : dp)
    		mx = max(mx, i);
     
    	cout << mx;
    }

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