Submission #1262858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262858		khanghb2006	Knapsack (NOI18_knapsack)	C++20	29 / 100	5 ms	328 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define TASK "task"

const int mxN = 5e5 + 7;
const int inf = 1e9 + 67;

struct item {
	int w , v , k;
}a[mxN];

int n;
int S;
long long sum = 0;
long long dp[3000];

void solve(void) {
	cin >> S >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].v >> a[i].w >> a[i].k;
		if(!a[i].w) sum += a[i].v * a[i].k;
	}
	memset(dp , -0x3f , sizeof dp);
	dp[0] = 0;
	for (int i = 1; i <= n; i++) {
		int W = a[i].w , V = a[i].v , K = a[i].k;
		for (int r = 0; r < W; r++) {
			deque<pair<int,int>> dq;
			for (int j = 0; r + j * W <= S; j++) {
				int c = r + j * W;
				long long val = dp[c] - 1LL * j * V;
				while(dq.size() && dq.back().first <= val) dq.pop_back();
				dq.emplace_back(val , j);
				while(dq.size() && j - dq.front().second > K) dq.pop_front();
				dp[c] = dq.front().first + 1LL * j * V;
			}
		}
	}
	long long ans = -inf;
	for (int i = 0; i <= S; i++)
		ans = max(ans , dp[i]);
	cout << ans;	
}

int main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	//freopen(TASK".inp","r",stdin);
	//freopen(TASK".out","w",stdout);
	int tc = 1;
	//cin >> tc;
	while(tc--) solve();
	return 0;
}

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