Submission #963314

#	Time	Username	Problem	Language	Result	Execution time	Memory
963314		bashNewbie	Knapsack (NOI18_knapsack)	C++17	73 / 100	1058 ms	4224 KiB

knapsack

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <climits>
#include <utility>
#include <stack>
using namespace std;

#define fast_io ios::sync_with_stdio(0), cin.tie(0)
#define pb push_back
#define sz(x) (int)x.size()
#define rng(x) begin(x), end(x)
template <typename T>
using vt = vector<T>;
using vi = vt<int>;
using pi = pair<int, int>;

const int N = 2e3+7, minf = INT_MIN;
int dp[N], cp[N], val[N];

bool cmp(int i, int j) {
	return val[i] > val[j];
}

void insert(stack<pi> &s, int x) {
	if(s.empty()) s.push({x, x}); else {
		auto [_, y] = s.top();
		s.push({x, cmp(x, y)? x: y});
	}
}

struct list {
	stack<pi> l, r;
	list(): l(), r() {}

	int top() {
		assert(size() > 0);
		int ret = -1;
		if(!l.empty()) {
			auto [_, x] = l.top();
			ret = x;
		}
		if(!r.empty()) {
			auto [_, x] = r.top();
			if(~ret) ret = cmp(ret, x)? ret: x; else
			ret = x;
		}
		return ret;
	}
	void push(int x) {
		insert(r, x);
	}
	void pop() {
		assert(size() > 0);
		if(l.empty()) {
			while(!r.empty()) {
				auto [x, _] = r.top();
				r.pop(), insert(l, x);
			}
		}
		l.pop();
	}
	size_t size() {
		return l.size()+r.size();
	}
	bool empty() {
		return size() == 0;
	}
};

list s[N];

void solve() {
	int m, n; cin >> m >> n;

	memset(dp, 0xff, sizeof(dp));
	dp[0] = 0;

	for(int i = 0; i < n; i++) {
		int v, w, k; cin >> v >> w >> k;

		memcpy(cp, dp, sizeof(cp));
		for(int j = 0; j < w; j++) s[j] = list();
		for(int j = 0; j < m+1; j++) {
			int r = j%w;
			val[j] = ~cp[j]? cp[j] - (j/w)*v: minf;
			s[r].push(j);

			if(s[r].size() > k+1) s[r].pop();
			int p = s[r].top(), x = (j-p)/w;
			dp[j] = ~cp[p]? cp[p] + x*v: -1;
		}
	}
	int ret = 0;
	for(int j = 0; j < m+1; j++) ret = max(ret, dp[j]);
	cout << ret << "\n";
}

int main() {
	fast_io;

	solve();
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:91:19: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   91 |    if(s[r].size() > k+1) s[r].pop();
      |       ~~~~~~~~~~~~^~~~~

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