Submission #1093023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093023		SilentCodr	Knapsack (NOI18_knapsack)	C++17	73 / 100	1086 ms	444 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) {
    scanf("%d%d", &w, &n);
    vector<int> dp(w + 1, -inf);
    dp[0] = 0;
    for (int _ = 0; _ < n; _++) {
        int val, wt, freq;
        scanf("%d%d%d", &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));
            }
        }
    }
    printf("%d", *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");
    }
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve(int)':
knapsack.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%d%d", &w, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~
knapsack.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf("%d%d%d", &val, &wt, &freq);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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