求 hack 或者证明

就是暴力加剪枝

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
	FILE *InFile=freopen("in_out/in.in","r",stdin),*OutFile=freopen("in_out/ans.ans","w",stdout);
#else
	FILE *InFile=stdin,*OutFile=stdout;
#endif
const int N=1e5;
struct O{int w,v;}cc[N];
long long f[N],cnt;
int main(){
	int n,c;scanf("%d%d",&n,&c);
	for(int i=1;i<=n;i++) scanf("%d%d",&cc[i].w,&cc[i].v);
	//sort(cc+1,cc+n+1,[](const O &a,const O &b){return a.w==b.w?a.v>b.v:a.w<b.w;}); 卡掉了下面的排序可以试试这个。
	sort(cc+1,cc+n+1,[](const O &a,const O &b){return a.v>b.v;});
	for(int i=1;i<=n;i++){
		bool con=1;
		for(int k=1;con;k++){
			con=0;
			for(int j=c-cc[i].w;j>=0;j--){
				if(f[j]+cc[i].v-2*k+1>f[j+cc[i].w])
					con=1,f[j+cc[i].w]=f[j]+cc[i].v-2*k+1;
				++cnt;
			}
		}
	}
	cerr<<cnt<<endl;
	printf("%lld",f[c]);
}