시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 386 | 126 | 96 | 41.379% |
농부는 $N$개의 꽃이 일렬로 활짝 핀 들판을 왼쪽에서 오른쪽으로 걷고 있다. 심심한 농부는 들판에 핀 꽃을 몇 개 따서 꽃다발을 만들려 한다.
꽃다발의 아름다움은 꽃을 딴 순서대로 놓았을 때 (인접한 꽃의 아름다움 차이)$^2$의 전체 합으로 정의된다.
산수를 어려워하는 농부는 가장 아름다운 꽃다발을 만들 수 있는 방법을 물어봤다. 농부가 만들 수 있는 꽃다발의 가장 높은 아름다움 값을 구해주자.
첫 번째 줄에 들판에 핀 꽃의 개수 $N$이 주어진다. ($2 \le N \le 100\,000$)
두 번째 줄에 $i$번째 꽃의 아름다움 값 $A_i$이 공백으로 구분되어 주어진다. ($1 \le A_i \le 100$)
꽃다발의 가장 높은 아름다움 값을 출력한다.
3 1 2 3
4
농부가 $A_1$, $A_2$, $A_3$을 따서 꽃다발을 만들면 꽃다발의 아름다움은 $(1-2)^2+(2-3)^2=2$다.
농부가 $A_1$, $A_3$을 따서 꽃다발을 만들면 꽃다발의 아름다움은 $(1-3)^2=4$다.
꽃을 하나만 따는 경우는 인접한 꽃이 없으므로 고려하지 않는다.