Submission #654279

#	Time	Username	Problem	Language	Result	Execution time	Memory
654279		thiago_bastos	Knapsack (NOI18_knapsack)	C++17	73 / 100	1097 ms	352 KiB

knapsack

#include "bits/stdc++.h"

using namespace std;

#define INF 1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define sc second
 
using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;	

const int N = 2e3 + 100;

i64 dp[N];
pair<i64, int> dq[N];

void solve() {
	int s, n;

	cin >> s >> n;

	fill(dp, dp + N, -INFLL);

	dp[0] = 0;

	for(int i = 0; i < n; ++i) {
		int v, w, c;

		cin >> v >> w >> c;

		for(int k = 0; k < w; ++k) {
			int lo = 0, hi = 0;

			for(int j = k; j <= s; j += w) {
				int l = (j - k) / w;
				i64 X = -INFLL;

				while(lo < hi && l - dq[lo].sc > c) ++lo;

				if(lo != hi) X = dq[lo].fi + 1ll * v * l;

				while(lo < hi && dq[hi - 1].fi < dp[j] - 1ll * v * l) --hi;

				dq[hi++] = {dp[j] - 1ll * v * l, l};

				dp[j] = max(dp[j], X);
			}
		}
	}

	cout << *max_element(dp, dp + N) << '\n';
}	

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
 //	cin >> t;
	while(t--) solve();
	return 0;
}

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