做法和第一二篇题解相同

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

#define ll long long
#define rep(i,x,y) for(ll i=x;i<=y;i++)

const ll M=1e9,C=1e5+5,N=30,L=3e7;
ll n,hp,l,seed,v[N],c[N],a[L];

void read() {
	cin>>n>>hp>>l>>seed;
	mt19937 rand(seed);

	rep(i,1,n) {
		v[i]=rand()%M+1;
		c[i]=rand()%C+1;
	}

	rep(i,1,l) {
		a[i]=rand()%n+1;
	}

//	cout<<"v:";
//
//	rep(i,1,n) {
//		cout<<v[i]<<' ';
//	}
//
//	cout<<"\nc:";
//
//	rep(i,1,n) {
//		cout<<c[i]<<' ';
//	}
//
//	cout<<"\na:";
//
//	rep(i,1,l) {
//		cout<<a[i]<<' ';
//	}
//
//	cout<<'\n';
}

const ll S=C*N<<1,inf=INT_MAX;
ll f1[S],f2[S];

void ini() {
	rep(i,1,S-1) {
		f1[i]=f2[i]=inf;
	}
}

bool b[N];

int main() {
	read();
	ini();
	ll sum=0,ans=0;

	rep(i,1,l) {
//		cout<<"sum="<<sum<<"\nhp="<<hp<<'\n';
		
		if(b[a[i]]==0) {
			b[a[i]]=1;

			for(ll j=S-1; j>=c[a[i]]; j--) {
				f1[j]=min(f1[j],f1[j-c[a[i]]]+v[a[i]]);
			}

			f2[S-1]=f1[S-1];

			for(ll j=S-2; j>=0; j--) {
				f2[j]=min(f2[j+1],f1[j]);
			}
		}

		sum+=v[a[i]];
		ll _sum=sum;

		if(hp<=0) {
//			cout<<"dying\n";
			ll tmp=-hp+1;

			if(tmp<S&&f2[tmp]!=inf) {
				sum-=f2[tmp];
			} else {
				break;
			}
		}

		ans=max(ans,sum);
		sum=_sum;
		hp-=c[a[i]];
	}

	cout<<ans;
}