import sys
input = sys.stdin.readline
N = int(input())
art = sorted([*map(int,input().split())] for i in range(N))
S = sum(art[i][1] for i in range(N))+art[0][0]-art[-1][0]
prefix1 = [0]; prefix2 = [0]
for i in range(N-1):
prefix1.append(prefix1[-1]+art[i+1][0]-art[i][0]-art[i][1])
prefix2.append(prefix2[-1]+art[-i-1][0]-art[-i-2][0]-art[-i-1][1])
arr1 = [(0,-1)]; arr2 = [(0,N)]
for i in range(1,N):
if prefix1[i] > arr1[-1][0]:
arr1.append((prefix1[i],i-1))
if prefix2[i] > arr2[-1][0]:
arr2.append((prefix2[i],N-i))
arr2.reverse()
MAX = 0; j = 0
for s,i in arr1:
for j in range(j,len(arr2)):
if arr2[j][1] <= i+1:
continue
MAX = max(MAX,s+arr2[j][0])
break
print(S+MAX)
누적합+스택을 이용하여 해결하였다.
풀이를 설명하면,
1. 모든 미술품이 포함되었을 때의 가치를 구하고, 미술품은 크기순으로 정렬한다.
2. 누적합을 이용하여 prefix1에는 미술품의 전체가치에서 1~i까지의 미술품을 제거했을 때 가치의 변화량을, prefix2에는 i~N까지의 미술품을 제거했을 때 가치의 변화량을 저장한다.
3. arr1과 arr2에 prefix1, prefix2에서 가치의 변화량이 이전보다 클 때와 그때의 인덱스 i를 순서대로 저장한다.
4. MAX를 0으로 시작해서 arr1의 첫번째부터 시작해서 만약 arr1의 가치변화량과 인덱스가 s,i라면 arr2에서 i+2 이상의 인덱스를 가진 값 중 가장 큰 값일때로 MAX를 갱신한다. (i+2 이상인 이유는 앞에서부터 i까지 제거했다면 i+1은 남겨두어야 하기 때문)
5. 모든 미술품이 포함되었을 때의 가치 + MAX를 출력한다.
풀이 자체는 간단한데, 인덱스를 처리하는 과정에서 실수가 많이 나왔던 문제였다.
오늘의 교훈) 실수를 줄이자.