ARC 036 B - 山のデータ

問題

問題概要

省略

解法

山の中央と決めて、その左右に条件を満たしながら、伸ばせるだけ伸ばした時がその時の山の最大となる。これを山の中央に対してすべて行うと TLEしてしまう。そこで、
if(h[mid - 1] < h[mid] && h[mid] > h[mid + 1])
という条件を加えると、TLEしなくなる。これは、答えとなる山は、少なくとも、上の条件を満たすからである。上の条件を満たさないものは、山の中央を左右に移動させたほうが、より大きな山になるからである。

ミス

TLE回避条件が難しかった。

コード

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

int n, h[300010];
int main(void){
    cin >> n;
    rep(i, n) cin >> h[i];
    int ans = 0;
    for (int mid = 0; mid < n; ++mid)
    {
        if(mid == 0 && mid == n - 1){
            if(mid == 0){
                int r =  mid;
                while(h[r] > h[r + 1] && r < n - 1) r++;
                ans = max(ans, r - mid + 1);
            }else{
                int l = mid;
                while(h[l - 1] < h[l] && 1 <= l) l--;
                ans = max(ans, mid - l + 1);
            }
        }else if(h[mid - 1] < h[mid] && h[mid] > h[mid + 1]){
            int l = mid, r = mid;
            while(h[l - 1] < h[l] && 1 <= l) l--;
            while(h[r] > h[r + 1] && r < n - 1) r++;

            ans = max(ans, r - l + 1);
        }
    }
    cout << ans << endl;
    return 0;
}