Submission #791830

#	Time	Username	Problem	Language	Result	Execution time	Memory
791830		Boomyday	Art Exhibition (JOI18_art)	Pypy 3	50 / 100	1085 ms	74792 KiB

art

bestScore = 0

N = int(input())

arts = []
INF = 10**18
for _  in range(N):
    a, b = map(int, input().split())
    arts.append((a, b))

arts.sort(key=lambda x: x[0])

A, B = [], []

for a, b in arts:
    A.append(a)
    B.append(b)


prefs = [0]

for i in range(N):
    prefs.append(prefs[-1] + B[i])


prefs_orig = prefs.copy()

for i in range(N):
    prefs[i+1] -= A[i]






suffix_maxs = [-INF]*(N+1)

suffix_maxs[-1] = prefs[-1]

for i in range(N-1, -1, -1):
    suffix_maxs[i] = max(suffix_maxs[i+1], prefs[i])


mx = max(B)

for st in range(N):
    bestmx = suffix_maxs[st+1]
    mx = max(mx, bestmx-prefs_orig[st]+A[st])

print(mx)

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 50