提出 #58261040

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 3e3 + 10;
const ll inf = 1e10;

int n, W;
int w; ll v;

vector<ll> rec[N];
priority_queue <ll, vector<ll>, less<ll> > pq;
ll f[N]; // f(i,j) 考虑小于等于 i 的权值(滚动数组)中，容量为 j 的最大价值
ll g[N]; // 在每一组中，选择 i 个物品的最大价值

int main(){
	cin >> n >> W;
	for(int i = 1; i <= n; i++){
		cin >> w >> v;
		rec[w].push_back(v); // 把价值按照权值分组
	}
	for(int i = 1; i <= W; i++){
		if(!rec[i].size()) continue;
		while(!pq.empty()) pq.pop();
		for(auto j : rec[i]){
			pq.push(j - 1);
		}
		for(int j = 1; j <= W / i; j++){
			g[j] = pq.top();
			pq.pop();
			pq.push(g[j] - 2);
			g[j] += g[j - 1];
		}
		for(int j = W; j >= i; j--){
			for(int k = 1; k <= j / i; k++){
				f[j] = max(f[j], f[j - k * i] + g[k]);
			}
		}
	}
	cout << f[W];
	return 0;
}

提出情報

ジャッジ結果