Submission #15170113


Source Code Expand

Copy
import sys
from heapq import heappush, heappop, heappushpop

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main(N, K, L, R):
    left = [[] for _ in range(N)]
    right = [[] for _ in range(N)]
    score = 0
    for k, l, r in zip(K, L, R):
        k -= 1
        if l < r:
            score += l
            right[k].append(r - l)
        else:
            score += r
            left[k].append(l - r)
    q = []
    for n, xs in enumerate(left, 1):
        for x in xs:
            if len(q) < n:
                heappush(q, x)
            else:
                heappushpop(q, x)
    score += sum(q)
    q = []
    for n, xs in enumerate(right[::-1][1:], 1):
        for x in xs:
            if len(q) < n:
                heappush(q, x)
            else:
                heappushpop(q, x)
    score += sum(q)
    return score

T = int(readline())
for _ in range(T):
    N = int(readline())
    K, L, R = [], [], []
    for _ in range(N):
        k, l, r = map(int, readline().split())
        K.append(k)
        L.append(l)
        R.append(r)
    print(main(N, K, L, R))

Submission Info

Submission Time
Task E - Camel Train
User maspy
Language Python (3.8.2)
Score 500
Code Size 1187 Byte
Status
Exec Time 595 ms
Memory 70404 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt
All 500 / 500 random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, sample_01.txt
Case Name Status Exec Time Memory
random_01.txt 202 ms 9428 KB
random_02.txt 192 ms 9320 KB
random_03.txt 221 ms 9932 KB
random_04.txt 197 ms 9812 KB
random_05.txt 221 ms 14980 KB
random_06.txt 278 ms 15408 KB
random_07.txt 228 ms 14148 KB
random_08.txt 270 ms 18892 KB
random_09.txt 337 ms 19776 KB
random_10.txt 303 ms 21460 KB
random_11.txt 587 ms 70260 KB
random_12.txt 580 ms 69900 KB
random_13.txt 579 ms 69788 KB
random_14.txt 575 ms 69688 KB
random_15.txt 585 ms 69796 KB
random_16.txt 595 ms 70348 KB
random_17.txt 595 ms 70404 KB
random_18.txt 577 ms 69628 KB
sample_01.txt 26 ms 9100 KB