Submission #58237301

---

Source Code Expand

// author: sendyuripics
// URL: https://atcoder.jp/contests/abc373/tasks/abc373_f
// created: 2024-09-28 20:00:16
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
void ts(){cout<<"IAKIOI\n";}
inline int read(){
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
int n,W,len;
int w[3005],v[3005];
int dp[3005][3005];
int com[3005],l[3005];
int now;
int get(int j,int i){return l[j]+(i-j)*(now-(i-j));}
void solve(int l,int r,int ql,int qr){
	if(l>r)return;
	int pm=ql;
	int mid=(l+r)/2;
	com[(l+r)/2]=get(pm,mid);
	for(int i=ql+1;i<=qr&&i<mid;i++){
		if(get(i,mid)>=com[mid]){
			pm=i,com[mid]=get(i,mid);
		}
	}
	solve(l,mid-1,ql,pm);solve(mid+1,r,pm,qr);
}
signed main(){
	n=read(),W=read();
	for(int i=1;i<=n;i++){
		w[i]=read(),v[i]=read();
	}
	//你考虑对于一个东西如果
	memset(dp,-0x3f,sizeof(dp));dp[0][0]=0;
	//对于第 (k+1)vi-(k+1)^(k+1)-kvi+k*k
	//delta=vi-2k-1.
	for(int i=1;i<=n;i++){
		for(int j=0;j<=W;j++)dp[i][j]=dp[i-1][j];
		//考虑这个
		for(int j=0;j<w[i];j++){
			len=0;
			now=v[i];
			for(int k=j;k<=W;k+=w[i])l[++len]=dp[i-1][k];
			len=0;
			for(int k=j;k<=W;k+=w[i])com[++len]=0;
			int pt=1;/*
			for(int k=1;k<=len;k++){
				//x=k-1. v[i]-1+l[x].
				//(k+1-x)*(v[i]-k+x-1)-(k-x)*(v[i]-(k-x));
				int cur=pt;
				for(int x=1;x<k;x++){
					if(l[x]+(k-x)*(v[i]-(k-x))>com[k]){
						com[k]=l[x]+(k-x)*(v[i]-(k-x));
						pt=x;
					}
				}
			}*/
			solve(1,len,1,len-1);
			for(int k=j;k<=W;k+=w[i])dp[i][k]=max(dp[i][k],com[(k-j)/w[i]+1]);
		}/*
		for(int j=0;j<=W;j++){
			for(int k=1;k*w[i]<=j;k++){
				//-((k-v[i]/2)^2)+v[i]*v[i]/4
				dp[i][j]=max(dp[i][j],dp[i-1][j-k*w[i]]+k*v[i]-k*k);
			}
		}*/
	}
	int res=0;
	for(int i=0;i<=W;i++)res=max(res,dp[n][i]);
	cout<<res<<"\n";
	return 0;
}
//look at my code
//my code is amazing

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:59:29: warning: unused variable ‘pt’ [-Wunused-variable]
   59 |                         int pt=1;/*
      |                             ^~

Judge Result