第９回日本情報オリンピック 本選 「つらら」

ちょっと考えたら解法が浮かんでくるのではないだろうか。

解法：
d[i]をi番目のつららの長さとする。
まず、一番長いつららd[i]が折れるのにかかる時間はL-d[i]である。

次に、二番目にながいつららについて、その両隣のどちらかに自分より長いつらら（つまり一番長いつらら）がある場合は”一番ながいつららの折れる時間” + ”二番目に長いつららの折れる時間"が二番目に長いつららが折れる時間となる。
両隣がどちらも自分より短い場合は”L - 自分のつららの長さ”　となる。

このように1番目にながいつららからN番目に長いつららの折れるまでにかかる時間をpriority_queueなどを使い、求めることができる。その折れる時間の最大値が解。

計算量はO(N).

#include <cstdio>
#include <queue>
#include <utility>
#include <algorithm>

using namespace std;
typedef pair<int,int> P;
int n,l,d[100003],s[100003];
int ans = 0;

int main(){
  scanf("%d%d",&n,&l);
  priority_queue<P> que;
  for(int i = 1;i <= n;i++){
    scanf("%d",&d[i]);
    que.push(P(d[i],i));
  }
  
  while(que.size()){
    P q = que.top(); que.pop();
    s[q.second] = max(s[q.second-1],s[q.second+1]) + l - q.first;
    ans = max(ans,s[q.second]);
  }
  printf("%d\n",ans);
  
  return 0;
}