Submission #1317336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317336		hansen	Knapsack (NOI18_knapsack)	C++20	100 / 100	34 ms	2944 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define test(v)            \
    for (auto &x : (v)) {       \
        cout << x << " ";       \
    }                           \
    cout << "\n";
#define test2d(v) \
    for (int i = 0; i < (int)v.size(); i++) { \
        for (int j = 0; j < (int)v[i].size(); j++) { \
            cout << v[i][j] << " "; \
        } \
        cout << '\n'; \
    }
#define pb push_back
vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
mt19937 rng((int)chrono::steady_clock::now().time_since_epoch().count());
int hashp = uniform_int_distribution<int>(10, 1e9)(rng);
int hashm1 = 1e9+7;
int hashm2 = 1e9+9;
int MOD = 1e9;
int MV = 1e18;

void solve(){
    int s, n;
    cin >> s >> n;
    vector<vector<array<int, 2>>> a(s+1);
    vector<int> dp(s+1, 0);
    for(int i = 0; i < n; i++){
        int v, w, k;
        cin >> v >> w >> k;
        a[w].pb({v, k});
    }
    for(int i = 1; i <= s; i++){
        if(a[i].empty()) continue;
        sort(a[i].begin(), a[i].end(), greater<>());
        vector<int> costs;
        int limit = s / i;
        for (auto &p : a[i]) {
            if (costs.size() >= limit) break;
            int val = p[0];
            int count = p[1];
            while (count > 0 && costs.size() < limit) {
                costs.pb(val);
                count--;
            }
        }
        for (size_t x = 1; x < costs.size(); x++) {
            costs[x] += costs[x-1];
        }
        for(int j = s; j >= i; j--){
            for(int k = 1; k <= costs.size(); k++){
                int prev_w = j - k * i;
                if (prev_w < 0) break;
                dp[j] = max(dp[j], dp[prev_w] + costs[k-1]);
            }
        }
    }
    cout << dp[s];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    /*
        freopen("snakes.in", "r", stdin);
        freopen("snakes.out", "w", stdout);
    */
    solve();
    return 0;
}

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