Submission #963262

#	Time	Username	Problem	Language	Result	Execution time	Memory
963262		bashNewbie	Knapsack (NOI18_knapsack)	C++17	73 / 100	1079 ms	1376 KiB

knapsack

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <climits>
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>;

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

class Compare {
public:
	bool operator() (int i, int j) {
		return val[i] < val[j];
	}
};

using pq = priority_queue<int, vi, Compare>;
pq q[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++) q[j] = pq();
		for(int j = 0; j < m+1; j++) {
			int r = j%w;
			val[j] = ~cp[j]? cp[j] - (j/w)*v: minf;
			q[r].push(j);

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

int main() {
	fast_io;

	solve();
}

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