README.md

[Gold III] 자석 - 28303

문제 링크

성능 요약

메모리: 134624 KB, 시간: 788 ms

분류

수학, 누적 합

제출 일자

2024년 7월 12일 20:05:32

문제 설명

동일한 크기의 정사각형 모양의 칸 N$N$개가 1$1$번부터 N$N$번까지 일렬로 배열된 실험대가 있다. 이 실험대의 i$i$번 칸에는 에너지 상수 ai$a_i$가 설정되어 있으며, 외부의 배터리와 연결되어 있다.

이하는 실험대에 일자 모양 자석 하나를 설치하려 한다. 자석의 크기는 2$2$부터 N$N$까지 이하가 임의로 설정할 수 있으며, 한쪽 끝에 한 칸 크기의 N극이 있고 반대쪽 끝에 한 칸 크기의 S극이 있다. 자석의 양 극은 각각 정확히 하나의 칸 위에 놓여야 한다.

자석을 실험대에 설치하면 배터리의 에너지가 변하는데, 다음 3가지 현상이 동시에 발생한다.

1. 자석의 N극이 놓인 칸의 에너지 상수만큼 배터리에 에너지가 충전된다.
2. 자석의 S극이 놓인 칸의 에너지 상수만큼 배터리의 에너지가 소모된다.
3. N극이 놓인 칸의 번호와 S극이 놓인 칸의 번호의 차에 K$K$를 곱한 만큼 배터리에서 에너지가 소모된다. 두 수의 차는 큰 수에서 작은 수를 뺀 값이다.

이하는 자석을 실험대에 설치하여 배터리를 최대한 충전하고 싶다. 이하를 도와 자석을 놓기 전과 비교해서 얻을 수 있는 배터리의 에너지 변화의 최댓값을 구해보자. 실험의 결과로 배터리의 에너지가 실험 전과 비교하여 감소할 수도 있다.

입력

첫 번째 줄에 두 정수 N$N$과 K$K$가 공백으로 구분되어 주어진다. (2≤N≤500000;0≤K≤2000)$(2\leq N\leq 500\, 000;0\leq K\leq 2\, 000)$ 

두 번째 줄에 N$N$개의 정수 a1,a2,⋯,aN$a_1,a_2,\cdots ,a_N$이 공백으로 구분되어 주어진다. (0≤ai≤109)$(0\leq a_i\leq 10^9)$ 

출력

첫 번째 줄에 자석을 놓기 전과 비교해서 얻을 수 있는 배터리의 에너지 변화의 최댓값을 출력한다.