旨いステーキ(Delicious Steak)

식초를 모든 스테이크에 뿌린 경우를 기준으로 잡으면 기본 점수는 $B=\sum_{i=1}^{3N}V_i$이다. $i$번째 스테이크에 A1소스를 뿌릴 때의 추가 점수는 $A_i-V_i$, 소금을 뿌릴 때의 추가 점수는 $S_i-V_i$이다.

스테이크를 $A_i-S_i$가 큰 순서대로 정렬하자. 앞쪽 스테이크에 소금, 뒤쪽 스테이크에 A1소스가 뿌려져 있다면 두 소스를 서로 바꿔도 총합은 감소하지 않는다. 따라서 최적해 중에는 A1소스가 뿌려진 스테이크가 모두 소금이 뿌려진 스테이크보다 앞에 있는 해가 존재한다.

A1소스를 선택하는 구간과 소금을 선택하는 구간 사이의 경계를 $k$라고 하자. $N\le k\le 2N$이다. 앞의 $k$개에서 $A_i-V_i$가 가장 큰 개를 선택한 추가 점수를 라고 하고, 뒤의 개에서 가 가장 큰 개를 선택한 추가 점수를 라고 하자. 구하는 답은 다음과 같다.

$$B+\max_{N\le k\le 2N}(P_k+Q_k).$$

최소 힙으로 모든 접두 구간의 $P_k$와 접미 구간의 $Q_k$를 구할 수 있다. 시간 복잡도는 $O(N\log N)$, 공간 복잡도는 이다. 정답은 절댓값이 이하이므로 64비트 정수를 사용한다.

Solution written by GPT6