0551-Icicles

問題概要

日本語なので略

解法

各つららにおいて長さが0になるまでの時間をa[x]とし，最初に全て0に初期化する．
次につららを長い順に見ていく．
長い順に見ているので，左右のつららを見てa[x+1]>0またはa[x-1]>0の場合はそのつららは，今見ているつららよりも長い．
よって，今見ているつららはmax(a[x+1],a[x-1])秒後に成長し始めることが分かるので，
a[x]=max(a[x+1],a[x-1])+L-つららの長さ
のようにして更新出来る．

全ての要素を見終わった後のaの要素の最大値が解となる．

実装(C++)

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef pair<int,int> P;
P data[100000];
int a[100001];
int ans=0;
int N,L;
int main() {
	scanf("%d%d",&N,&L);
	for(int i=0;i<N;i++){
		int t;
		scanf("%d",&t);
		data[i].first=L-t;
		data[i].second=i;
	}
	std::sort(data,data+N);
	for(int i=0;i<N;i++){
		a[data[i].second+1]=max<int>(a[data[i].second],a[data[i].second+2])+data[i].first;
		ans=max(ans,a[data[i].second+1]);
	}
	printf("%d\n",ans);
	return 0;
}