D. Bear and Blocks

Implementation

출처: Codeforces D. Bear and Blockss

SOL)
 N^2은 Time limit 한 열이 모두 사라지는 것은 왼쪽, 오른쪽, 자기 스스로
이렇게 3가지에 영향을 받는다. 한번에 조사가 가능하다.


[-] Collapse

#include<stdio.h>
#include<algorithm>
using namespace std;
int t[100002];
int r[100002];
int n, ans;
int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &t[i]);

    for (int i = 1; i <= n; i++)
        r[i] = min(r[i - 1] + 1, t[i]); //왼쪽에서 없어지는 경우 or 하나씩 없어지는 경우

    for (int i = n; i >= 1; i--)
        r[i] = min(r[i], r[i + 1] + 1); //오른쪽 or 왼쪽

    for (int i = 1; i <= n; i++)
        ans = max(ans, r[i]);
    printf("%d", ans);
    return 0;

}