Submission #1093016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093016		SilentCodr	Knapsack (NOI18_knapsack)	C++17	73 / 100	1081 ms	1616 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define nl '\n'
int n, m, k, p, q, u, v, w, l, r, x, y, z;
// #define int long long
const int N = 1e3 + 10, inf = 1e9, mod = 998244353;

mt19937_64 randll(chrono::steady_clock::now().time_since_epoch().count());
vector<vector<char>> dp;

void solve (int tc = 1) {
    cin >> w >> n;
    vector<int> dp(w + 1, -inf);
    dp[0] = 0;
    for (int _ = 0; _ < n; _++) {
        int val, wt, freq;
        cin >> val >> wt >> freq;
        freq = min(freq, w);
        for (int md = 0; md < wt; md++) {
            deque<pair<int, int>> q;
            for (int i = md; i <= w; i += wt) {
                while (!q.empty() and q.front().second < i - wt * freq) q.pop_front();
                int oval = dp[i];
                if (!q.empty()) {
                    dp[i] = max(dp[i], (i - q.front().second) / wt * val + q.front().first);
                }
                while (!q.empty() and q.back().first + (i - q.back().second) / wt * val < oval) q.pop_back();
                q.push_back(make_pair(oval, i));
            }
        }
    }
    cout << *max_element(dp.begin(), dp.end());
}
    
#undef int

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tc = 1;

    // cin >> tc;
    // scanf("%d", &tc);
    while (tc--) {
        solve(tc);
        if (tc) cout << nl;
        // if (tc) printf("\n");
    }
}

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