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 .

Solution (Python):

from heapq import heappush, heappop
import sys
def main(N, KLR):
    LL = [(-(l - r), k - 1) for k, l, r in KLR if l >= r and k < N]
    RR = [(-(r - l), N - k - 1) for k, l, r in KLR if l < r and k < N]
    ans = sum(l for k, l, r in KLR if k >= N)
    ans += sum(min(l, r) for k, l, r in KLR if k != N)
    for L in (LL, RR):
        M = len(L)
        L.sort(key=lambda x: x[1], reverse=True)
        q = []
        j = 0
        for i in range(N - 1, -1, -1):
            while j < M and L[j][1] >= i:
                heappush(q, L[j][0])
                j += 1
            if q:
                ans += -heappop(q)
    return ans

if __name__ == '__main__':
    input = sys.stdin.readline
    T = int(input())
    for i in range(T):
        N = int(input())
        KLR = [tuple(map(int, input().split())) for _ in range(N)]
        ans = main(N, KLR)
        print(ans)

Solution (Python):
import heapq

T = int(input())

for _ in range(T):
  N = int(input())
  res = 0
  Ls,Rs = [[] for _ in range(N)], [[] for _ in range(N)]
  for _ in range(N):
    K,L,R = map(int,input().split())
    m = min(L,R)
    res += m
    L -= m
    R -= m
    if L>0:
      Ls[K-1].append(L)
    else:
      if K != N:
        Rs[K].append(R)


  pq1 = []
  for i in reversed(range(N)):
    for l in Ls[i]:
      heapq.heappush(pq1, -l)
    if pq1:
      p = -heapq.heappop(pq1)
      res += p

  pq2 = []
  for i in range(N):
    for r in Rs[i]:
      heapq.heappush(pq2, -r)
    if pq2:
      p = -heapq.heappop(pq2)
      res += p

  print(res)

Solution (Python):

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()

Solution (Python):
t = int(input())
ans = []

for tt in range(t):
    n = int(input())

    redk = {}
    bluek = {}
    asum = 0
    for i in range(n):
        k,l,r = list(map(int,input().split()))
        asum += min(l,r)
        if l >= r:
            if k in redk:
                redk[k].append(l-r)
            else:
                redk[k] = [l-r]
        else:
            if k in bluek:
                bluek[k].append(r-l)
            else:
                bluek[k] = [r-l]
    reds = []
    for i in range(1,n+1):
        if i in redk:
            reds += redk[i]
        while len(reds) > i:
            reds.remove(min(reds))
    blues = []
    for i in range(n,0,-1):
        if i in bluek:
            blues += bluek[i]
        while len(blues) >= n + 1 - i:
            blues.remove(min(blues))
    ans.append(asum + sum(reds) + sum(blues))

for i in range(len(ans)):
    print(ans[i])

Solution (Python):


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()

Solution (Python):


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()

Solution (Python):


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)
            
            if k < 0: continue
            val += diff
            vis[k] = k - 1


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

        ans.append(val)

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



if __name__ == "__main__":
    resolve()

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
def resolve():
    
    
    
    
    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()

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
import sys
input = sys.stdin.buffer.readline




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()))


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()
		

		Q=[]
		heapq.heapify(Q)

		for k,v in L:
			ans+=v
			heapq.heappush(Q,v)
			if len(Q)>k:
				
				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:
				
				vv=heapq.heappop(Q)
				ans-=vv
		print(ans)






if __name__ == "__main__":
	main()

Solution (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()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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())

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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))

Solution (Python):
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')

Solution (Python):
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')

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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()