AOJ 0551: Icicles

つらら

汚いです。
やるだけで、実装が(自分にとっては)難しい問題だと思ったけど、考える問題らしい。余裕があるときに解きなおしたい。
long使う必要なかったかも。面倒臭いから全部longにしちゃったけど。

long n,l,ice[100002],ict[100002],icf[100002],irs[100002];
long tp[100002];

int main(){
	int f = 0;
	cin>>n>>l;
	for(int i = 1; i <= n; i++){
		cin>>ice[i];
	}
	for(int i = 1; i <= n; i++){
		ict[i] = l - ice[i];
	}
	for(int i = 1; i <= n; i++){
		icf[i] = ((ice[i]<ice[i-1]) << 1) + (ice[i]<ice[i+1]);
	}
	for(int i = 1; i <= n; i++){
		if(!icf[i]){
			irs[i] = ict[i];
			tp[f] = i;
			f++;
		}
	}
	for(int i = 0; i < f; i++){
		icf[tp[i]-1] &= ~1;
		icf[tp[i]+1] &= ~2;
		tp[i] = 0;
	}
	while(f){
		f = 0;
		for(int i = 1; i <= n; i++){
			if(!irs[i] && !icf[i]){
				if(ice[i]<ice[i-1] && ice[i]<ice[i+1]){
					irs[i] = ict[i] + max(irs[i-1],irs[i+1]);
				}else {
					irs[i] = ict[i] + (ice[i-1]>ice[i+1] ? irs[i-1] : irs[i+1]);
				}
				tp[f] = i;
				f++;
			}
		}
		for(int i = 0; i < f; i++){
			icf[tp[i]-1] &= ~1;
			icf[tp[i]+1] &= ~2;
			tp[i] = 0;
		}
	}
	long r = 0;
	for(int i = 1; i <= n; i++){
		r = max(r,irs[i]);
	}
	cout<<r<<endl;
	return 0;
}