Submission #747445

#	Time	Username	Problem	Language	Result	Execution time	Memory
747445		Can_I_Put_ma_ballz	Art Exhibition (JOI18_art)	Cpython 3	0 / 100	13 ms	2900 KiB

art

import sys

def isprime(x):
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            return False
    return True

def cmp(i, j):
    return i > j

def cmp2(i, j):
    if i[0] == j[0]:
        return i[1] > j[1]
    return i[0] < j[0]

def main():
    n = int(input())
    a = []
    ans = 0
    sum = 0
    for _ in range(n):
        x, y = map(int, input().split())
        a.append((x, y))
        sum += y
    a.sort(key=lambda x: (-x[0], x[1]))

    l = 0
    r = n - 1
    while l <= r:
        ans = max(ans, sum - (a[r][0] - a[l][0]))
        if l != r:
            ml = (sum - a[l][1]) - (a[r][0] - a[l + 1][0])
            mr = (sum - a[r][1]) - (a[r - 1][0] - a[l][0])
            if ml > mr:
                sum -= a[l][1]
                l += 1
            else:
                sum -= a[r][1]
                r -= 1
        else:
            break

    print(ans)

if __name__ == '__main__':
    main()

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