제출 #1050349

#제출 시각아이디문제언어결과실행 시간메모리
1050349vjudge1Art Exhibition (JOI18_art)Cpython 3
0 / 100
10 ms2908 KiB
def maximize_exhibition_value(N, artworks):
    artworks.sort()

    max_value = float('-inf')
    current_sum = 0
    left = 0

    for right in range(N):
        current_sum += artworks[right][1]

        A_max = artworks[right][0]
        A_min = artworks[left][0]
        current_value = current_sum - (A_max - A_min)

        max_value = max(max_value, current_value)

        while left < right and (current_sum - artworks[left][1]) - (artworks[right][0] - artworks[left + 1][0]) >= current_value:
            current_sum -= artworks[left][1]
            left += 1
            A_min = artworks[left][0]
            current_value = current_sum - (A_max - A_min)
            max_value = max(max_value, current_value)

    return max_value

N = int(input())
artworks = []
for _ in range(N):
    A, B = map(int, input().split())
    artworks.append((A, B))

result = maximize_exhibition_value(N, artworks)
print(result)
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...