Problem:


Score : 500 points

Problem Statement

We have N camels numbered 1,2,\ldots,N.
Snuke has decided to make them line up in a row.

The happiness of Camel i will be L_i if it is among the K_i frontmost camels, and R_i otherwise.

Snuke wants to maximize the total happiness of the camels. Find the maximum possible total happiness of the camel.

Solve this problem for each of the T test cases given.

Constraints

All values in input are integers.

1 \leq T \leq 10^5

1 \leq N \leq 2 \times 10^{5}

1 \leq K_i \leq N

1 \leq L_i, R_i \leq 10^9

The sum of values of N in each input file is at most 2 \times 10^5.

Input

Input is given from Standard Input in the following format:

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

Each case is given in the following format:

N
K_1 L_1 R_1
\vdots
K_N L_N R_N

Output

Print T lines. The i-th line should contain the answer to the i-th test case.

Sample Input 1

3
2
1 5 10
2 15 5
3
2 93 78
1 71 59
3 57 96
19
19 23 16
5 90 13
12 85 70
19 67 78
12 16 60
18 48 28
5 4 24
12 97 97
4 57 87
19 91 74
18 100 76
7 86 46
9 100 57
3 76 73
6 84 93
1 6 84
11 75 94
19 15 3
12 11 34

Sample Output 1

25
221
1354

In the first test case, it is optimal to line up the camels in the order 2, 1.

Camel 1 is not the frontmost camel, so its happiness will be 10.

Camel 2 is among the two frontmost camels, so its happiness will be 15.

In the second test case, it is optimal to line up the camels in the order 2, 1, 3.

Camel 1 is among the two frontmost camels, so its happiness will be 93.

Camel 2 is the frontmost camel, so its happiness will be 71.

Camel 3 is among the three frontmost camels, so its happiness will be 57.



Sample input:
3
2
1 5 10
2 15 5
3
2 93 78
1 71 59
3 57 96
19
19 23 16
5 90 13
12 85 70
19 67 78
12 16 60
18 48 28
5 4 24
12 97 97
4 57 87
19 91 74
18 100 76
7 86 46
9 100 57
3 76 73
6 84 93
1 6 84
11 75 94
19 15 3
12 11 34


Sample output:
25
221
1354

Submission status: Accepted

Solution code:
# E - Camel Train
import sys
from heapq import heappop, heappush

readline = sys.stdin.buffer.readline


def maximize_happiness() -> int:
    res = 0
    lefty, righty = [], []

    N = int(readline())
    for _ in range(N):
        k, l, r = map(int, readline().split())
        if k == N or l == r:
            res += l
        elif l > r:
            res += l
            lefty.append((k, l - r))
        else:
            res += r
            righty.append((N - k, r - l))

    for camels in [lefty, righty]:
        camels.sort()
        heap = []
        for k, diff in camels:
            heappush(heap, diff)
            if k < len(heap):
                res -= heappop(heap)

    return res


def main():
    T = int(readline())
    res = [maximize_happiness() for _ in range(T)]
    print("\n".join(map(str, res)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    ans = []
    for i in range(T):
        N = next(it)

        val = 0
        a1 = [[] for i in range(N)];
        a2 = [[] for i in range(N)];
        for i, v1, v2 in ((next(it)-1, next(it), next(it)) for i in range(N)):
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                    else:
                        diff = heappushpop(dq, diff)

            val += sum(dq)

        ans.append(val)


    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    ans = []
    for i in range(T):
        N = next(it)

        val = 0; a1 = []; a2 = []
        for i, v1, v2 in ((next(it), next(it), next(it)) for i in range(N)):
            diff = v1 - v2
            if diff == 0:
                val += v1
            elif diff > 0:
                a1.append((i, diff))
                val += v2
            else:
                a2.append((N-i, -diff))
                val += v1
        a1.sort(); a2.sort()

        for aa in (a1, a2):
            dq = []
            for i, diff in aa:
                ld = len(dq)
                if ld < i:
                    heappush(dq, diff)
                else:
                    diff = heappushpop(dq, diff)

            val += sum(dq)

        ans.append(val)


    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
sys.setrecursionlimit(1000000000)

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    ans = []
    for i in range(T):
        N = next(it)

        val = 0; a1 = []; a2 = []
        for i, v1, v2 in ((next(it), next(it), next(it)) for i in range(N)):
            diff = v1 - v2
            a, v, diff = (a1, v2, diff) if diff >= 0 else (a2, v1, -diff)
            a.append((diff, i))
            val += v
        a1.sort(reverse=True); a2.sort(reverse=True)

        ls = len(a1)
        vis = [None]*(N+1)
        def root(x):
            if vis[x] == None: return x

            vis[x] = root(vis[x])
            return vis[x]
        def root(x):
            a = []
            while True:
                y = vis[x]
                if y == None:
                    break
                a.append(x)
                x = y
            for i in a:
                vis[i] = x
            return x

        for diff, i in a1:
            j = min(i, ls) - 1
            k = root(j)
            #print(diff, i, j, k,  vis)
            if k < 0: continue
            val += diff
            vis[k] = k - 1


        for diff, i in a2:
            j, v2 = max(i, ls), [[-1]]
            k = root(j)
            #print(diff, i, j, k,  vis)
            if k >= N: continue
            val += diff
            vis[k] = k + 1

        ans.append(val)

    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import heapq

def solve():
    n = int(input())
    hp = 0
    ord_l = [[] for _ in range(n)]
    ord_r = [[] for _ in range(n)]
    bd_l, bd_r = 0, 0
    for _ in range(n):
        k, l, r = map(int, input().split())
        if k == n:
            hp += l
            continue
        if l == r:
            hp += l
            continue

        hp += min(l, r)
        if l > r:
            ord_l[k-1].append(l-r)
            bd_l = max(bd_l, k)
        else:
            ord_r[k].append(r-l)
            bd_r = max(bd_r, n-k)

    ord_l = ord_l[:bd_l][::-1]
    ord_r = ord_r[-bd_r:]

    left = []
    heapq.heapify(left)
    for i in range(bd_l):
        for x in ord_l[i]:
            heapq.heappush(left, -x)
        if left:
            hp += (heapq.heappop(left)*(-1))
    
    right = []
    heapq.heapify(right)
    for i in range(bd_r):
        for x in ord_r[i]:
            heapq.heappush(right, -x)
        if right:
            hp += (heapq.heappop(right)*(-1))
    print(hp)


def main():
    t = int(input())
    for _ in range(t):
        solve()

main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

sc = map(int, open(0).read().split())
ni = lambda: next(sc)

def solve(A):
    Q = []
    for i, ai in enumerate(A):
        for aij in ai:
            heappush(Q, aij)
        while len(Q) > i:
            heappop(Q)
    return sum(Q)

T = ni()
for _ in range(T):
    N = ni()
    A, B = [[] for _ in range(N + 1)], [[] for _ in range(N + 1)]

    ans = 0
    for _ in range(N):
        k, l, r = ni(), ni(), ni()
        if l >= r:
            A[k].append(l - r)
        else:
            B[k].append(r - l)
        ans += min(l, r)

    ans += solve(A) + solve(reversed(B))
    print(ans)

Submission status: Accepted

Solution code:
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]
    import heapq 

    t=int(input())
    for i in range(t):
        n=int(input())
        L=[[] for _ in range(n)]
        R=[[] for _ in range(n)]
        lm,rm=-1,-1
        ans=0
        for j in range(n):
            k,l,r=map(int,input().split())
            ans+=min(l,r)
            if l-r>=0:
                L[k-1].append(r-l)
                lm=max(lm,k-1)
            else:
                if n-k-1>=0:
                    R[n-k-1].append(l-r)
                    rm=max(rm,n-k-1)
        q=[]
        heapq.heapify(q)
        if lm>-1:
            for j in range(lm,-1,-1):
                for k in L[j]:
                    heapq.heappush(q,k)
                if q:
                    ans-=heapq.heappop(q)
        q=[]
        heapq.heapify(q)
        if rm<n:
            for j in range(rm,-1,-1):
                for k in R[j]:
                    heapq.heappush(q,k)
                if q:
                    ans-=heapq.heappop(q)
        print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def solve():
    N = int(input())

    left = [[] for _ in range(N + 1)]
    right = [[] for _ in range(N + 1)]

    left_len = 0

    s = 0
    for _ in range(N):
        k, l, r = map(int, input().split())
        k -= 1

        mi = min(l, r)
        l -= mi
        r -= mi

        s += mi
        if r:
            k = N - 2 - k
            if k < 0: continue
            right[k].append(r)
        else:
            left[k].append(l)
            left_len += 1

    def additional_happiness(src, len_):
        """src: 二重リスト, 設置可能な位置の制約が厳しい->緩い順の候補リスト
        """
        from heapq import heappop, heappush

        ret = 0

        h = []
        while len(src) > len_:
            cands = src.pop()
            for v in cands:
                heappush(h, -v)

        for cands in reversed(src):
            for v in cands:
                heappush(h, -v)
            if h:
                x = heappop(h)
                ret -= x
        return ret

    s += additional_happiness(left, left_len)
    s += additional_happiness(right, N - left_len)

    return s


def main():
    import sys
    input = sys.stdin.readline

    T = int(input())

    ans = []
    for _ in range(T):
        res = solve()
        ans.append(res)

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

def greedy(limit, n):
    ans = 0
    hq = []
    for i in range(n-1, -1, -1):
        for item in limit[i]:
            # 最大値を取り出したいので負で格納
            heapq.heappush(hq, -item)
        if hq:
            ans += -heapq.heappop(hq)
    return ans

def solve():
    n = int(input())
    left = []
    limit_l = [[] for i in range(n)]
    l_cnt = 0
    right = []
    limit_r = [[] for i in range(n)]
    r_cnt = 0
    ans = 0
    for i in range(n):
        k, l, r = map(int, input().split())
        ans += min(l, r)
        if l > r:
            # 左に並びたい
            limit_l[k-1].append(l-r)
            l_cnt+=1
        else:
            # 右に並びたい
            if n-k-1 >= 0:
                limit_r[n-k-1].append(r-l)
            else:
                # 右のスコアを獲得できない
                pass
            r_cnt+=1
    ans += greedy(limit_l, n)
    ans += greedy(limit_r, n)
    print(ans)
    return 

t = int(input())
for i in range(t):
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import heapq

def main():
	t=II()
	for _ in range(t):
		n=II()
		L=[]
		R=[]
		ans=0
		for _ in range(n):
			k,l,r=MI()
			if l>=r:
				ans+=r
				L.append((k,l-r))
			else:
				ans+=l
				R.append((n-k,r-l))
		L.sort()
		R.sort()
		#print(L,R,ans)

		Q=[]
		heapq.heapify(Q)

		for k,v in L:
			ans+=v
			heapq.heappush(Q,v)
			if len(Q)>k:
				#print(Q,k,ans)
				vv=heapq.heappop(Q)
				ans-=vv

		Q=[]
		heapq.heapify(Q)

		for k,v in R:
			ans+=v
			heapq.heappush(Q,v)
			if len(Q)>k:
				#print(Q,k,ans)
				vv=heapq.heappop(Q)
				ans-=vv
		print(ans)






if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python

import sys
input = sys.stdin.buffer.readline
from collections import deque
from heapq import heappush, heappop, heapify
sys.setrecursionlimit(10**6)

def main():
    T = int(input())
    for ti in range(T):
        ans = 0
        N = int(input())
        L,R = [],[]
        for _ in range(N):
            k,l,r = map(int,input().split())
            ans += min(l,r)
            if l > r:
                L.append((l-r,k))
            elif l < r:
                if N-k > 0:
                    R.append((r-l,N-k))
        L.sort(key=lambda x: x[1])
        R.sort(key=lambda x: x[1])
        LC = deque(L)
        RC = deque(R)

        H = []
        for i in range(1,N+1):
            while LC and LC[0][1] == i:
                heappush(H, LC.popleft())
            while len(H) > i:
                heappop(H)
        while H:
            ans += heappop(H)[0]

        H = []
        for i in range(1,N+1):
            while RC and RC[0][1] == i:
                heappush(H, RC.popleft())
            while len(H) > i:
                heappop(H)
        while H:
            ans += heappop(H)[0]
        
        print(ans)
        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

def calc(camels, N):
    camels.sort(key=lambda x: x[0])
    heap = []
    for i, x in camels:
        heappush(heap, x)
        if len(heap) > i:
            heappop(heap)
    return sum(heap)

T = int(input())
for _ in range(T):
    N = int(input())
    s = 0
    ans = 0
    first = []
    second = []
    for i in range(N):
        K, L, R = map(int, input().split())
        if L >= R:
            first.append((K, L - R))
            ans += R
        else:
            second.append((N - K, R - L))
            ans += L
    ans += calc(first, N) + calc(second, N)
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heappush, heappushpop
import sys
input = sys.stdin.readline

def calc(camels):
    camels = deque(sorted(camels, key=lambda x: x[0]))
    N = len(camels)
    heap = []
    while camels and camels[0][0] == 0:
        camels.popleft()
    for i in range(1, N+1):
        while camels and camels[0][0] == i:
            _, x = camels.popleft()
            if len(heap) < i:
                heappush(heap, x)
            elif heap[0] < x:
                heappushpop(heap, x)
    for _, x in camels:
        if len(heap) < N:
            heappush(heap, x)
        elif heap[0] < x:
            heappushpop(heap, x)
    return sum(heap)

T = int(input())
for _ in range(T):
    N = int(input())
    s = 0
    ans = 0
    first = []
    second = []
    for i in range(N):
        K, L, R = map(int, input().split())
        if L >= R:
            first.append((K, L - R))
            ans += R
        else:
            second.append((N - K, R - L))
            ans += L
    ans += calc(first) + calc(second)
    print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from heapq import heappop, heappush
def solve():
    N = int(input())
    Ls = [[] for _ in range(N)]
    Rs = [[] for _ in range(N)]
    base = 0
    for _ in range(N):
        k, l, r = mapint()
        if l>=r:
            Ls[k-1].append(l-r)
            base += r
        else:
            if N-k!=0:
                Rs[N-k-1].append(r-l)
            base += l
    return base + calculate(Ls, N) + calculate(Rs, N)


def calculate(lis, N):
    queue = []
    for i in range(N):
        for x in lis[i]:
            heappush(queue, x)
        while len(queue)>i+1:
            heappop(queue)
    return sum(queue)


T = int(input())
for t in range(T):
    print(solve())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import heapq
from operator import itemgetter

T=int(input())
for tests in range(T):
    N=int(input())
    C=[tuple(map(int,input().split())) for i in range(N)]

    ANS=0
    LEFT=[]
    RIGHT=[]
    
    for k,l,r in C:
        if l>r:
            ANS+=r
            LEFT.append((k,l-r))
        else:
            ANS+=l
            RIGHT.append((k,r-l))

    LEFT.sort(key=itemgetter(0),reverse=True)
    H=[]
    ind=0

    for i in range(N,0,-1):
        while ind<len(LEFT) and LEFT[ind][0]>=i:
            heapq.heappush(H,-LEFT[ind][1])
            ind+=1

        if H:
            ANS+=-heapq.heappop(H)

    RIGHT.sort(key=itemgetter(0))
    H=[]
    ind=0

    for i in range(N):
        while ind<len(RIGHT) and RIGHT[ind][0]<=i:
            heapq.heappush(H,-RIGHT[ind][1])
            ind+=1

        if H:
            ANS+=-heapq.heappop(H)

    print(ANS)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappushpop

readline = sys.stdin.readline


def solve():
    N = int(readline())

    left = [[] for _ in range(N)]
    right = [[] for _ in range(N)]
    ans = 0
    for _ in range(N):
        K, L, R = map(int, readline().split())
        if L > R:
            ans += R
            left[K - 1].append(L - R)
        else:
            ans += L
            if 0 <= N - K - 1:
                right[N - K - 1].append(R - L)

    for vec in (left, right):
        hq = []
        n = len(vec)

        for i in range(n):
            for p in vec[i]:
                if len(hq) >= i + 1:
                    heappushpop(hq, p)
                else:
                    heappush(hq, p)

        for i in range(n, N):
            for p in vec[i]:
                if len(hq) >= n:
                    heappushpop(hq, p)
                else:
                    heappush(hq, p)

        ans += sum(hq)

    return ans


def main():
    T = int(readline())

    ans = [0] * T
    for i in range(T):
        ans[i] = solve()

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq


def solve(a):
    pq = list()
    heapq.heapify(pq)
    delta = 0
    k = 0
    for i in range(len(a)):
        for x in a[i]:
            if k <= i:
                delta += x
                heapq.heappush(pq, x)
                k += 1
            elif pq:
                delta += x
                heapq.heappush(pq, x)
                delta -= heapq.heappop(pq)
    return delta


t = int(input())
while t > 0:
    t -= 1
    n = int(input())
    left = [list() for i in range(n)]
    right = [list() for i in range(n)]
    ans = 0
    for i in range(n):
        k, l, r = map(int, input().split())
        if l > r:
            left[k - 1].append(l - r)
        elif l < r:
            if k < n:
                right[n - 1 - k].append(r - l)
        ans += min(l, r)
    print(ans + solve(left) + solve(right))

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    res = 0
    camel_left, camel_right = [], []
    for _ in range(N):
        K, L, R = map(int, rl().split())
        res += min(L, R)
        if R <= L:
            camel_left.append([K, L, R])
        elif K != N:
            camel_right.append([N - K, L, R])
    
    camel_left.sort(key=itemgetter(0))
    camel_right.sort(key=itemgetter(0))
    
    hq = []
    i = 0
    for j in range(1, N + 1):
        while i < len(camel_left) and camel_left[i][0] == j:
            heappush(hq, camel_left[i][1] - camel_left[i][2])
            i += 1
        while j < len(hq):
            heappop(hq)
    res += sum(hq)
    
    hq = []
    i = 0
    for j in range(1, N):
        while i < len(camel_right) and camel_right[i][0] == j:
            heappush(hq, camel_right[i][2] - camel_right[i][1])
            i += 1
        while j < len(hq):
            heappop(hq)
    res += sum(hq)
    
    return res


if __name__ == '__main__':
    T = int(rl())
    ans = []
    for _ in range(T):
        ans.append(solve())
    print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from heapq import *

def solve(p:list):
    s = 0
    n = len(p)
    data = [[] for _ in range(n+1)]
    for i,j in p:
        data[min(i,n)].append(j)
    H = []
    heapify(H)
    for i in range(n,0,-1):
        for j in data[i]:
            heappush(H,-j)
        if H:
            s -= heappop(H)
    return s
    
t = int(input())
for _ in range(t):
    n = int(input())
    ans = 0
    pl = []
    pr = []
    for _ in range(n):
        k,l,r = map(int,input().split())
        m = min(l,r)
        ans += m
        l,r = l-m,r-m
        if l:
            pl.append((k,l))
        else:
            pr.append((n-k,r))
    print(ans+solve(pl)+solve(pr))

Submission status: Accepted

Solution code:
T = int(input())

import heapq

def calc(camels):
	camels.sort()
	camels.reverse()
	count = len(camels)
	
	score = 0
	queue = []
	i = 0
	for k in range(count, 0, -1):
		while i < count and camels[i][0] >= k:
			K, L, R = camels[i]
			heapq.heappush(queue, (-(L - R), L, R))
			i += 1
		if len(queue) > 0:
			D, L, R = heapq.heappop(queue)
			score += L
	while len(queue) > 0:
		D, L, R = heapq.heappop(queue)
		score += R
	while i < count:
		K, L, R = camels[i]
		score += R
		i += 1
	return score

for t in range(T):
	N = int(input())
	
	camels_l = []
	camels_r = []
	
	count_r = 0
	for _ in range(N):
		K, L, R = map(int, input().split())
		if L - R >= 0:
			camels_l.append((K, L, R))
		else:
			camels_r.append((N - K, R, L))
	
	print(calc(camels_l) + calc(camels_r))

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

readline = sys.stdin.readline


def solve():
    N = int(readline())

    left = [[] for _ in range(N)]
    right = [[] for _ in range(N)]
    ans = 0
    for _ in range(N):
        K, L, R = map(int, readline().split())
        if L > R:
            ans += R
            left[K - 1].append(L - R)
        else:
            ans += L
            if 0 <= N - K - 1:
                right[N - K - 1].append(R - L)

    for vec in (left, right):
        hq = []
        n = len(vec)

        for i in range(n):
            for p in vec[i]:
                heappush(hq, p)
            while len(hq) > i + 1:
                heappop(hq)

        for i in range(n, N):
            for p in vec[i]:
                heappush(hq, p)
            while len(hq) > n:
                heappop(hq)

        ans += sum(hq)

    return ans


def main():
    T = int(readline())

    ans = [0] * T
    for i in range(T):
        ans[i] = solve()

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

readline = sys.stdin.readline


def solve():
    N = int(readline())

    left = [[] for _ in range(N)]
    right = [[] for _ in range(N)]
    ans = 0
    for _ in range(N):
        K, L, R = map(int, readline().split())
        if L > R:
            ans += R
            left[K - 1].append(L - R)
        else:
            ans += L
            if 0 <= N - K - 1:
                right[N - K - 1].append(R - L)

    for vec in (left, right):
        hq = []
        n = len(vec)
        for idx in range(N):
            for p in vec[idx]:
                heappush(hq, p)
            while len(hq) > min(idx + 1, n):
                heappop(hq)

        ans += sum(hq)

    return ans


def main():
    T = int(readline())

    ans = [0] * T
    for i in range(T):
        ans[i] = solve()

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

readline = sys.stdin.readline


def solve():
    N = int(readline())

    left = [[] for _ in range(N)]
    right = [[] for _ in range(N)]
    ans = 0
    for _ in range(N):
        K, L, R = map(int, readline().split())
        if L > R:
            ans += R
            left[K - 1].append(R - L)
        else:
            ans += L
            if 0 <= N - K - 1:
                right[N - K - 1].append(L - R)

    for vec in (left, right):
        hq = []
        n = len(vec)
        for idx in range(N - 1, -1, -1):
            for p in vec[idx]:
                heappush(hq, p)
            if idx < n and hq:
                ans -= heappop(hq)

    return ans


def main():
    T = int(readline())

    ans = [0] * T
    for i in range(T):
        ans[i] = solve()

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

readline = sys.stdin.readline


def solve():
    N = int(readline())

    left = []
    right = []
    ans = 0
    for _ in range(N):
        K, L, R = map(int, readline().split())
        if L > R:
            ans += R
            left.append((K - 1, R - L))
        else:
            ans += L
            right.append((N - K - 1, L - R))

    for vec in (left, right):
        vec.sort()
        hq = []
        for idx in range(len(vec) - 1, -1, -1):
            while vec and idx <= vec[-1][0]:
                heappush(hq, vec.pop()[1])
            if hq:
                ans -= heappop(hq)

    return ans


def main():
    T = int(readline())

    ans = [0] * T
    for i in range(T):
        ans[i] = solve()

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
t = int(input())
for _ in range(t):
    n = int(input())
    lefts = [[] for _ in range(n)]
    rights = [[] for _ in range(n)]
    ans = 0
    for i in range(n):
        k, l, r = map(int, input().split())
        k -= 1
        if l >= r:
            ans += r
            lefts[k].append(l-r)
        else:
            ans += l
            rights[k].append(r-l)
    l_queue = []
    heapq.heapify(l_queue)
    for i in range(n):
        for j in range(len(lefts[i])):
            ans += lefts[i][j]
            heapq.heappush(l_queue,lefts[i][j])
        while len(l_queue) > i+1:
            m = heapq.heappop(l_queue)
            ans -= m
    r_queue = []
    heapq.heapify(r_queue)
    for i in range(n):
        for j in range(len(rights[n-i-1])):
            ans += rights[n-i-1][j]
            heapq.heappush(r_queue, rights[n-i-1][j])
        while len(r_queue) > i:
            m = heapq.heappop(r_queue)
            ans -= m
    print(ans)

Submission status: Accepted

Solution code:
import heapq
T=int(input())
for _ in range(T):
    N=int(input())
    lq=[[] for _ in range(N+1)]
    rq=[[] for _ in range(N+1)]
    ans=0
    for _ in range(N):
        K,L,R=map(int,input().split())
        ans+=min(L,R)
        if L>R:
            lq[K].append(L-R)
        else:
            rq[K].append(R-L)
    ls=[]
    for i in range(1,N+1):
        for v in lq[i]:
            heapq.heappush(ls,v)
        while len(ls)>i:
            heapq.heappop(ls)
    ans+=sum(ls)
    rs=[]
    for i in range(N,0,-1):
        for v in rq[i]:
            heapq.heappush(rs,v)
        while len(rs)>N-i:
            heapq.heappop(rs)
    ans+=sum(rs)
    print(ans)