Submission #1131890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131890		ngtlong	Knapsack (NOI18_knapsack)	C++20	0 / 100	1 ms	324 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long
#define eb emplace_back
#define task ""
#define get_bit(mask, i) mask & (1 << i)
#define set_bit(mask, i) mask | (1 << i)
#define mas(a, n) a + 1, a + n + 1
#define cts(a) a.begin(), a.end()

const int narr = 1e5 + 5;
const ll oo = 1e18;
const int inf = 1e9;

using namespace std;

void testcase() {
	#ifndef ONLINE_JUDGE
	freopen("tmp.inp", "r", stdin);
	freopen("tmp.out", "w", stdout);
	#endif
}

void readfo() {
	freopen(task".inp", "r", stdin);
	freopen(task".out", "w", stdout);
}

ll knapsack(ll n, ll W, ll w[], ll v[], ll q[]) {
    vector<ll> dp(W + 1, 0);
	ll weight, value, quantity, index, currentValue;
    for (ll i = 1; i <= n; i++) {
        weight = w[i], value = v[i], quantity = q[i];
        if (weight > W) continue;
        for (ll mod = 0; mod < weight; mod++) {
            deque<pair<ll, ll>> dq;
            for (ll currentWeight = mod; currentWeight <= W; currentWeight += weight) {
                index = currentWeight / weight, currentValue = dp[currentWeight] - index * value;
                while (!dq.empty() && dq.back().first <= currentValue)
                    dq.pop_back();
                dq.eb(currentValue, currentWeight);
                if (!dq.empty() && dq.front().second < currentWeight - quantity * weight)
                    dq.pop_front();
                dp[currentWeight] = dq.front().first + index * value;
            }
        }
    }

    return dp[W];
}


ll w[narr], v[narr], q[narr], n, W;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	testcase();
	// readfo();
	cin >> W >> n;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> q[i];
    cout << knapsack(n, W, w, v, q) << "\n";
	cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}
// Code written by longdegea

Compilation message (stderr)

knapsack.cpp: In function 'void testcase()':
knapsack.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen("tmp.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen("tmp.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp: In function 'void readfo()':
knapsack.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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