Colopl programming contest 2018 : D - すぬけそだて――トレーニング――

Cまでは良かったがそこからが微妙だった。
https://colopl2018-qual.contest.atcoder.jp/tasks/colopl2018_qual_d

問題

初期状態でスタミナがXある。
以後、時間1毎にスタミナが1回復する。ただしXを超えることはない。

途中N回のタイミングT[i]でトレーニングを行える。
このタイミングでは残量が負にならない範囲で任意量のスタミナを消費し、その分知力を上げる。
トレーニングを行うタイミングをK=1～N個選択するとき、それぞれ得られる知力の総量はいくらか。

解法

f(i,j) := i回目のタイミングまでにj回トレーニングを行った時の知力増加量
とする。もとめたいのはf(N,K)である。

f(i,j)は当然ながらf(*,j-1)のどこからか遷移するので、直前に行ったトレーニングをk回目の物とすると
f(i,j)=min(f(k,j-1)+min(X,T[i]-T[k]))
となる。
よってf(k,j-1)+Xおよびf(k,j-1)-T[k]のそれぞれに対しRMQを行えるようにしておけば、f(*,*)をO(N^2*logN)で埋められる。

int N;
ll X,T[10101];
ll dp[5050][5050];
int pre[5050];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	FOR(i,N) cin>>T[i+1];
	for(i=1;i<=N;i++) {
		while(T[i]-T[pre[i]+1]>=X) pre[i]++;
	}
	
	FOR(x,N+1) FOR(y,N+1) dp[x][y]=-1LL<<60;
	dp[0][0]=0;
	for(i=1;i<=N;i++) {
		
		ll ma=0;
		int L=0;
		ll a=X,b=-1LL<<60;
		deque<pair<ll,int>> D;
		//D.push_back({dp[i-1][0]-0,0});
		for(x=1;x<=N;x++) {
			
			while(L+1<=pre[x]) {
				L++;
				a=max(a,dp[i-1][L]+X);
			}
			while(D.size() && D.front().second<=pre[x]) D.pop_front();
			
			dp[i][x]=a;
			if(D.size()) dp[i][x]=max(a,D.front().first+T[x]);
			
			ma=max(ma,dp[i][x]);
			ll add=dp[i-1][x]-T[x];
			while(D.size() && D.back().first<=add) D.pop_back();
			D.push_back({add,x});
		}
		cout<<ma<<endl;
		
	}
}

まとめ

600ptでもいいかなとも思ったけど、これで500ptなのね。