LOJ6039 「雅礼集训 2017 Day5」珠宝

// Problem: #6039. 「雅礼集训 2017 Day5」珠宝 /「NAIPC2016」Jewel Thief
// Contest: LibreOJ
// URL: https://loj.ac/p/6039
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 50050;

ll n, m, f[310][maxn], g[maxn], h[maxn], K;
vector<ll> a[maxn], b[maxn];

void dfs(int l, int r, int pl, int pr, int k) {
	if (l > r || pl > pr) {
		return;
	}
	int mid = (l + r) >> 1, p = -1;
	for (int i = max(pl, mid - (int)a[k].size()); i <= min(mid, pr); ++i) {
		ll val = g[i] + b[k][mid - i];
		if (val > h[mid]) {
			h[mid] = val;
			p = i;
		}
	}
	dfs(l, mid, pl, p, k);
	dfs(mid + 1, r, p, pr, k);
}

void solve() {
	scanf("%lld%lld", &n, &m);
	for (int _ = 0, x, y; _ < n; ++_) {
		scanf("%d%d", &x, &y);
		a[x].pb(y);
	}
	for (int i = 1; i <= 300; ++i) {
		sort(a[i].begin(), a[i].end(), greater<ll>());
		ll s = 0;
		b[i].pb(0);
		for (ll x : a[i]) {
			s += x;
			b[i].pb(s);
		}
	}
	for (int i = 1; i <= 300; ++i) {
		for (int j = 0; j < i; ++j) {
			K = 0;
			for (int k = j; k <= m; k += i) {
				g[++K] = f[i - 1][k];
				h[K] = -1e18;
			}
			dfs(1, K, 1, K, i);
			for (int k = j, t = 1; k <= m; k += i, ++t) {
				f[i][k] = h[t];
			}
		}
	}
	for (int i = 1; i <= m; ++i) {
		printf("%lld ", f[300][i]);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}