Submission #875940

#	Time	Username	Problem	Language	Result	Execution time	Memory
875940		MDSPro	Knapsack (NOI18_knapsack)	C++17	100 / 100	692 ms	11464 KiB

knapsack

// MDSPro
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

const ld PI = 3.141592653589793;
const int MOD = 1e9+7;
const int INF = 1e9;
const ll INFLL = 4e18;
const double EPS = 1e-9;
const int MAXN = 1000*1007;

void solve(int NT){
    int s, n; cin >> s >> n;
    vector<pair<int, int>> a;
    for(int i = 0; i < n; ++i) {
        int v, w, k; cin >> v >> w >> k;

        int cur = 1;
        do {
            k -= cur;

            long long nv = 1LL * cur * v, nw = 1LL * cur * w;
            if(nw <= s && nv <= 2e9) a.emplace_back(nv, nw);
            cur = min(2 * cur, k);
        } while(k > 0);
    }

    n = a.size();

    vector<long long> dp(s + 1);
    for(int i = 0; i < n; ++i) {
        auto [v, w] = a[i];
        for(int j = s; j >= w; --j) {
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }

    cout << *max_element(dp.begin(), dp.end());
}

// #define TESTCASES
int main() {
    cin.tie(0)->sync_with_stdio(0);

    int t = 1;
    #ifdef TESTCASES
        cin >> t;
    #endif
    
    for(int i = 1; i <= t; ++i){
        solve(i);
        cout << "\n";
    }
}

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