제출 #1164678

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164678		crispxx	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	504 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define pb push_back
#define ar array
#define nl '\n'

void solve() {
	int S, n; cin >> S >> n;
	
	vector<int> dp(S + 1);
	
	for(int i = 0; i < n; i++) {
		int v, w, k; cin >> v >> w >> k;
		
		vector<int> new_dp = dp;
		
		for(int y = 0; y < w; y++) {
			deque<ar<int, 2>> dq;
			for(int x = 0; x * w + y <= S; x++) {
				int j = x * w + y, G = dp[j] - v * x;
				
				while(!dq.empty() && G >= dp[dq.back()[0]] - v * dq.back()[1]) {
					dq.pop_back();
				}
				dq.push_back({j, x});
				
				while(!dq.empty() && x - dq.front()[1] > k) {
					dq.pop_front();
				}
				
				new_dp[j] = max(new_dp[j], dp[dq.front()[0]] + v * (x - dq.front()[1]));
			}
		}
		
		dp = new_dp;
	}
	
	cout << dp[S] << nl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt = 1;
	// cin >> tt;
	while(tt--) solve();
}

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