Submission #1350632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1350632		vjudge1	Knapsack (NOI18_knapsack)	C++20	49 / 100	6 ms	452 KiB

knapsack

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ft first
#define sd second
using namespace std;
using namespace __gnu_pbds;
using bs = bitset<8000>;
const ll it = 4e18;
const int MAXN = 1e6 + 5;
const int MOD = 1e9 + 7;
const int MAXK = 40005;
const ll I = 1e9;
const ll INF = 1e18;
const int m = 1e5 + 5;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int S, N;
    scanf("%d %d", &S, &N);
    vector<ll> dp(S + 1, 0);
    for (int i = 0; i < N; ++i) {
        int v, w, k;
        scanf("%d %d %d", &v, &w, &k);
        if (w == 0) continue;            
        if (k * w >= S) {             
            for (int j = w; j <= S; ++j)
                dp[j] = max(dp[j], dp[j - w] + v);
        } else {                       
            for (int r = 0; r < w; ++r) {
                deque<int> dq;             
                deque<ll> vals;         
                for (int j = r; j <= S; j += w) {
                    ll be = dp[j] - (j / w) * (ll)v;
                    while (!vals.empty() && vals.back() <= be) {
                        vals.pop_back();
                        dq.pop_back();
                    }
                    vals.push_back(be);
                    dq.push_back(j);
                    if (dq.front() < j - k * w) {
                        dq.pop_front();
                        vals.pop_front();
                    }
                    dp[j] = vals.front() + (j / w) * (ll)v;
                }
            }
        }
    }
    printf("%lld\n", dp[S]);
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d %d", &S, &N);
      |     ~~~~~^~~~~~~~~~~~~~~~~
knapsack.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%d %d %d", &v, &w, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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