0551:Icicles

つららの長さがすべて0になるまでの時間を求める。
lをつららの長さの上限として、

dp[i]:=i番目のつららの長さa[i]がlになるまでの時間

if(a[i]>a[i-1] && a[i]>a[i+1])dp[i] = l-a[i]
else dp[i] = max(dp[i-1], dp[i+1]) + l-a[i]

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n,l,dp[100005],a[100005];

int func(int i){

  if(i>n)return 0;
  if(dp[i]>0)return dp[i];

  int res=0;
  if(a[i]<a[i-1])res=max(res,func(i-1));
  if(a[i]<a[i+1])res=max(res,func(i+1));

  return dp[i]=l-a[i]+res;
}

int main(void){
  
  while(cin >> n >> l){
    
    for(int i=0;i<n+2;i++)dp[i]=0;

    for(int i=1;i<n+1;i++)
      cin >> a[i];

    a[0]=a[n+1]=0;

    int res=0;
    for(int i=1;i<n+1;i++)
      res=max(res,func(i));

    cout << res << endl;
  }
  
  return 0;
}