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: Wrong Answer

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:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i
                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: Wrong Answer

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
                a2[i].append(-diff)
                val += v1

        for aa in (a1, a2):
            for i, aa in enumerate(aa):
                dq = []
                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: Wrong Answer

Solution code:
import heapq as hq

T = int(input())
for _ in range(T):
    N = int(input())
    camels = [list(map(int, input().split())) for _ in range(N)]
    base = 0
    camels_L = [[] for _ in range(N+1)]
    camels_R = [[] for _ in range(N+1)]
    for camel in camels:
        if camel[1] >= camel[2]:
            camels_L[camel[0]].append(camel[1] - camel[2])
            base += camel[2]
        else:
            camels_R[N - camel[0]].append(camel[2] - camel[1])
            base += camel[1]

            diff = 0

    heap_camels = []
    hq.heapify(heap_camels)
    for i in range(1, N+1):
        for camel in camels_L[i]:
            hq.heappush(heap_camels, camel)
        while len(heap_camels) > i:
            hq.heappop(heap_camels)
    diff += sum(heap_camels)

    heap_camels = []
    hq.heapify(heap_camels)
    for i in range(1, N+1):
        for camel in camels_R[i]:
            hq.heappush(heap_camels, camel)
        while len(heap_camels) > i:
            hq.heappop(heap_camels)
    diff += sum(heap_camels)
    print(diff + base)

Submission status: Wrong Answer

Solution code:
import heapq as hq

T = int(input())
for _ in range(T):
    N = int(input())
    camels = [list(map(int, input().split())) for _ in range(N)]
    base = 0
    camels_L = [[] for _ in range(N+1)]
    camels_R = [[] for _ in range(N+1)]
    
for camel in camels:
    if camel[1] >= camel[2]:
        camels_L[camel[0]].append(camel[1] - camel[2])
        base += camel[2] # LとRの低いほうを加算
    else:
        camels_R[N - camel[0]].append(camel[2] - camel[1])
        base += camel[1]

diff = 0

heap_camels = []
hq.heapify(heap_camels)
for i in range(1, N+1):
    # 左からi番目までが限度のラクダをまとめて追加
    for camel in camels_L[i]:
        hq.heappush(heap_camels, camel)
        # 左からi番目までに入りきらない場合に低いものから除外
    while len(heap_camels) > i:
        hq.heappop(heap_camels)
        # heapqに残ったものがすべての条件を満たしうれしさが最大
diff += sum(heap_camels)

        # Rラクダについても同様
heap_camels = []
hq.heapify(heap_camels)
for i in range(1, N+1):
    for camel in camels_R[i]:
        hq.heappush(heap_camels, camel)
    while len(heap_camels) > i:
        hq.heappop(heap_camels)
diff += sum(heap_camels)
print(diff + base)

Submission status: Wrong Answer

Solution code:
def max():
    S=[]
    N=int(input())
    cases=[list(map(int,input().split())) for i in range(N)]
    Li=[]
    Ri=[]
    for case in cases:
        if case[1]>=case[2]:
            Li.append(case)
        else:
            Ri.append(case)
    L=[]
    a=0
    for j in range(1,N+1):
      if j==N:
        for l in Li:
          L.append(l)  
      else:  
        for l in Li:
          if l[0]<=j:
            L.append(l)
            a+=1
            #print("a:",a)
            #print("j:",j)
            #print("del前のL:",L)
            if len(L)>j:
              while len(L)>j:
                min=L[0][1]-L[0][2]
                k=0
                for i in range(len(L)):
                  if L[i][1]-L[i][2]<min:
                    k=i
                    min=L[i][1]-L[i][2]
                L.remove(L[k])
                a-=1
                #print("a:",a)
                #print("del後のL:",L)
              #print("Li:",len(Li))
      if a!=0:
        for i in range(1,a+1):
          Li.remove(L[-i])
        a=0
        #print("remove後のLi;",Li)
    #print("finish L:",L)
    
    R=[]
    for j in range(1,N+1):
      if j==N:
        for r in Ri:
          R.append(r)  
      else:  
        for r in Ri:
          if r[0]<=j:
            R.append(r)
            a+=1
            #print("j:",j)
           # print("del前のR:",R)
            if len(R)>j:
              while len(R)>j:
                min=R[0][2]-R[0][1]
                k=0
                for i in range(len(R)):
                  if R[i][2]-R[i][1]<min:
                    k=i
                    min=R[i][2]-R[i][1]
                R.remove(R[k])
                a-=1
              #print("del後のR:",R)
              #print("Ri:",len(Ri))
          if a==1:
            for i in range(1,a+1):
              Ri.remove(R[-i])
            a=0
            #print("remove後のRi;",Ri)
    #print("finish R:",R)
    
    sum=0
    S=L+R
    #print("L:",L,"R:",R)
    for j in range(len(S)):
        if S[j][0]>=j+1:
            sum+=S[j][1]
            
        else:
            sum+=S[j][2]
            
    print(sum)

T=int(input())
for i in range(T):
    max()

Submission status: Wrong Answer

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: Wrong Answer

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)

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

Submission status: Wrong Answer

Solution code:
def max():
    S=[]
    N=int(input())
    cases=[list(map(int,input().split())) for i in range(N)]
    Li=[]
    Ri=[]
    for case in cases:
        if case[1]>=case[2]:
            Li.append(case)
        else:
            Ri.append(case)
            
    for j in range(1,N+1):
        for l in Li:
            if l[0]==j:
                S.append(l)
            while len(S)>j:
                min=S[0][1]-S[0][2]
                k=0
                for i in range(len(S)):
                    if S[i][1]-S[i][2]<min:
                        k=i
                        min=S[i][1]-S[i][2]
                del S[k]
    le=len(S)            
    for j in range(1,N+1):
        for R in Ri:
            if R[0]==j:
                S.append(R)
            while len(S)>j+le:
                min=S[0][2]-S[0][1]
                k=0
                for i in range(len(S)):
                    if S[i][2]-S[i][1]<min:
                        k=i
                        min=S[i][2]-S[i][1]
                del S[k]
    sum=0
    for j in range(len(S)):
        if S[j][0]>=j+1:
            sum+=S[j][1]
            
        else:
            sum+=S[j][2]
            
    print(sum)

T=int(input())
for i in range(T):
    max()

Submission status: Wrong Answer

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

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

        for i in range(1,N+1):
            H = []
            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: Wrong Answer

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 _ in range(T):
        ans = 0
        # input
        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)

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

        for i in range(1,N+1):
            H = []
            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: Wrong Answer

Solution code:
import heapq
t = int(input())
for _ in range(t):
    n = int(input())
    klr = [tuple(map(int, input().split())) for _ in range(n)]
    klr.sort()
    left = []
    score = 0
    for K, L, R in klr:
        if K != n:
            score += R
            if R < L:
                heapq.heappush(left, L-R)
        else:
            score += L

        if len(left) <= K:
            continue
        heapq.heappop(left)
    score += sum(left)
    print(score)

Submission status: Wrong Answer

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]:
            queue.append(x)
        while len(queue)>i+1:
            heappop(queue)
    return sum(queue)


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

Submission status: Wrong Answer

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[::-1], N)


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


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

Submission status: Wrong Answer

Solution code:
from heapq import *

def solve():
  N=int(input())
  X,Y=[[] for i in range(N)],[[] for i in range(N)]
  k,l,r=0,0,0
  P=0
  for i in range(N):
    k,l,r=map(int,input().split())
    P+=min(l,r)
    if l>=r:
      X[k-1].append(l-r)
    else:
      if k!=N:
        Y[-k].append(r-l)
  Q=[]
  heapify(Q)
  for i in range(N):
    for j in range(len(X[i])):
      heappush(Q,X[i][j])
    while i+1<len(Q):
      heappop(Q)
  while len(Q):
    P+=heappop(Q)
  for i in range(N):
    for j in range(len(Y[i])):
      heappush(Q,Y[i][j])
    while i+1<len(Q):
      heappop(Q)
  while len(Q):
    P+=heappop(Q)
  print(P)

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

Submission status: Wrong Answer

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: Wrong Answer

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):
            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: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n=1):
        self.parent = [i for i in range(n)]
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    
    def union(self, x, y): # x -> y
        x = self.find(x)
        y = self.find(y)
        self.parent[x] = y
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)


def solve(KLR):
  res = 0
  N = len(KLR)
  left = UnionFind(N+1)
  right = N
  DKLR = [(abs(l-r), k, l, r) for k, l, r in KLR]
  DKLR.sort(reverse=True)
  for _, k, l, r in DKLR:
    if l < r:
      if k < right:
        res += r
      else:
        res += l
      right -= 1
    elif l > r:
      idx = left.find(k)
      if idx:
        res += l
        _idx = left.find(idx-1)
        left.union(idx, _idx)
      else:
        res += r
        right -= 1
    else:
      res += l
  return res


ans = []
T = int(input())
for i in range(T):
  N = int(input())
  KLR = [tuple(map(int, input().split())) for i in range(N)]
  ans.append(solve(KLR))

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque


def main():
    T = int(sys.stdin.readline().rstrip())  # テストケース数

    for _ in range(T):
        N = int(sys.stdin.readline().rstrip())

        pnt = 0
        LC = []
        RC = []
        for n in range(N):
            k, l, r = map(int, sys.stdin.readline().rstrip().split())

            # left と right に分ける
            if l > r:
                LC.append((k, r - l))  # 加点を増やす／sort用には正負反転
                pnt += min(l, r)
            else:
                RC.append((N - k, l - r))  # 右から何番目までに登録するか
                pnt += min(l, r)

        LC.sort()
        RC.sort()
        # print(LC)
        # print(RC)
        # print(pnt)
        LC = deque(LC)
        RC = deque(RC)

        # Left 側
        S, T = [], []
        # tmp = 0
        for j in range(1, N + 1):
            # print(j)
            while LC:
                # 位置がjのものを取り出す
                if LC[0][0] == j:
                    # print(LC)
                    if len(S) < j:
                        pnt += -1 * LC[0][1]
                        # tmp += -1 * LC[0][1]
                        S.append(LC[0])
                    else:
                        T.append(LC[0])
                    LC.popleft()
                else:
                    break
        # print(S, T)

        # print(tmp)

        # Right側
        S, T = [], []
        # tmp = 0
        for j in range(N):
            # print(j)
            while RC:
                # 位置がjのものを取り出す
                if RC[0][0] == j:
                    # print(RC)
                    if len(S) < j:
                        pnt += -1 * RC[0][1]
                        # tmp += -1 * RC[0][1]
                        S.append(RC[0])
                    else:
                        T.append(RC[0])
                    RC.popleft()
                else:
                    break

        # print(S, T)
        # print(tmp)
        print(pnt)


main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque


def main():
    T = int(sys.stdin.readline().rstrip())  # テストケース数

    for _ in range(T):
        N = int(sys.stdin.readline().rstrip())

        pnt = 0
        LC = []
        RC = []
        for n in range(N):
            k, l, r = map(int, sys.stdin.readline().rstrip().split())

            # left と right に分ける
            if l > r:
                LC.append((k, r - l))  # 加点を増やす／sort用には正負反転
                pnt += min(l, r)
            else:
                RC.append((N - k, l - r))  # 右から何番目までに登録するか
                pnt += min(l, r)

        LC.sort()
        RC.sort()
        # print(LC)
        # print(RC)
        # print(pnt)
        LC = deque(LC)
        RC = deque(RC)

        # Left 側
        S = 0  #
        tmp = 0
        for j in range(1, N + 1):
            while LC:
                # 位置がjのものを取り出す
                if LC[0][0] == j:
                    if S < j:
                        pnt += -1 * LC[0][1]
                        tmp += -1 * LC[0][1]
                        S += 1
                    LC.popleft()
                else:
                    break

        # print(tmp)

        # Right側
        S = 0
        tmp = 0
        for j in range(N):
            while RC:
                # 位置がjのものを取り出す
                if RC[0][0] == j:
                    if S < j:
                        pnt += -1 * RC[0][1]
                        tmp += -1 * RC[0][1]
                        S += 1
                    RC.popleft()
                else:
                    break

        # print(tmp)
        print(pnt)


main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque


def main():
    T = int(sys.stdin.readline().rstrip())
    for t in range(T):
        N = int(sys.stdin.readline().rstrip())
        pnt = 0

        tmp_pnt = 0

        LC = []
        RC = []
        for n in range(N):
            k, l, r = map(int, sys.stdin.readline().rstrip().split())

            tmp_pnt += max(l, r)

            # 左寄せと右寄せに分ける
            if l > r:
                LC.append((k, r - l))  # 加点を増やす／正負反転して登録
                pnt += min(l, r)
            else:
                RC.append((N - k, l - r))  # 減点を減らす
                pnt += min(l, r)

        LC.sort()
        RC.sort()
        LC = deque(LC)
        RC = deque(RC)

        # Left 側
        S = 0  #
        tmp_pnt = 0
        for j in range(1, N + 1):
            while LC:
                # 位置がjのものを取り出す
                if LC[0][0] == j:
                    if S < j:
                        pnt += -1 * LC[0][1]
                        tmp_pnt += -1 * LC[0][1]
                        S += 1
                    LC.popleft()
                else:
                    break

        # Right側
        S = 0
        tmp_pnt = 0
        for j in range(N):
            while RC:
                # 位置がjのものを取り出す
                if RC[0][0] == j:
                    if S < j:
                        pnt += -1 * RC[0][1]
                        tmp_pnt += -1 * RC[0][1]
                        S += 1
                    RC.popleft()
                else:
                    break

        print(pnt)


main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque


def main():
    T = int(sys.stdin.readline().rstrip())
    for t in range(T):
        N = int(sys.stdin.readline().rstrip())
        C = []
        pnt = 0

        tmp_pnt = 0

        LC = []
        RC = []
        i = 0
        for n in range(N):
            k, l, r = map(int, sys.stdin.readline().rstrip().split())

            tmp_pnt += max(l,r)

            # 左寄せと右寄せに分ける
            if l > r:
                LC.append((k, r - l))  # 加点を増やす／正負反転して登録
                pnt += min(l,r)
            else:
                RC.append((N - k, l - r))  # 減点を減らす
                pnt += min(l,r)
            # print(i, pnt)

        # print("基本点", pnt)
        # print("最大点", tmp_pnt)

        LC.sort()
        RC.sort()

        # print(LC)
        # print(RC)

        LC = deque(LC)
        RC = deque(RC)

        S = 0  #
        tmp_pnt = 0
        for j in range(1, N+1):
            while LC:
                # 位置がjのものを取り出す
                if LC[0][0] == j:
                    # print(LC[0])
                    if S < j:
                        # print("Count")
                        pnt += -1 * LC[0][1]
                        tmp_pnt += -1 * LC[0][1]
                        S += 1
                    else:
                        # print("No Count")
                        pass
                    LC.popleft()
                else:
                    break

        # print("LC加点", tmp_pnt)

        S = 0  #
        tmp_pnt = 0

        # print(RC)

        for j in range(N):
            while RC:
                # 位置がjのものを取り出す
                if RC[0][0] == j:
                    # print(RC[0])
                    if S < j:
                        # print("Count")
                        pnt += -1 * RC[0][1]
                        tmp_pnt += -1 * RC[0][1]
                        S += 1
                    else:
                        # print("No Count")
                        pass
                    RC.popleft()
                else:
                    break

        # print("RC加点", tmp_pnt)
        print(pnt)


main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    n = int(input())
    score = 0
    front = []
    rear = []
    for _ in range(n):
        K, L, R = map(int, input().split())
        if K != n:
            score += min(L, R)
            if R < L:
                front.append((K, R-L))
            elif L < R:
                rear.append((K+1, R-L))
        else:
            score += L
    front.sort()
    rear.sort(reverse=True)
    for i in range(len(front)):
        if i+1 <= front[i][0]:
            score += -front[i][1]

    for i in range(len(rear)):
        if rear[i][0] <= n-i:
            score += rear[i][1]

    print(score)

Submission status: Wrong Answer

Solution code:
import heapq  
def priority(klr):
    return abs(klr[1]-klr[2])
              
def process(KLR):
    ans = 0   
    q = []    
    for klr in KLR:
        pr = priority(klr)
        if klr[0] < len(q) and q[0][0] < pr:
            pr_tmp0, klr_tmp = heapq.heappop(q)
            ans += min(klr_tmp[1], klr_tmp[2])
        if klr[0] >= len(q):
            heapq.heappush(q, (pr, klr))
    for pr, klr in q:
        ans += max(klr[1], klr[2])
    return ans
              
              
def solve():  
    N = int(input())
    KLR = []  
    for _ in range(N):
        klr = list(map(int, input().split()))
        klr[0] -= 1 # convert to 0-based index to avoid confusion                                                                                                                                           
        KLR.append(klr)
    ans = 0   
    KLR_L = []
    KLR_R = []
    for klr in KLR:
        if klr[1] > klr[2]:
            KLR_L.append(klr)
        elif klr[1] < klr[2]:
            klr[0] = N-1-klr[0]-1
            if klr[0] < 0:
                ans += min(klr[1], klr[2])
            else:
                KLR_R.append(klr)
        else: 
            ans += klr[1]
    KLR_L.sort(key=lambda klr: klr[0])
    KLR_R.sort(key=lambda klr: klr[0])
    ans += process(KLR_L)
    ans += process(KLR_R)
    print(ans)
              
T = int(input())
              
for _ in range(T):
    solve()

Submission status: Wrong Answer

Solution code:
import heapq  
def priority(klr):
    return abs(klr[1]-klr[2])
              
def process(KLR):
    ans = 0   
    q = []    
    for klr in KLR:
        pr = priority(klr)
        if klr[0] < len(q) and q[0][0] < pr:
            pr, klr_tmp = heapq.heappop(q)
            ans += min(klr_tmp[1], klr_tmp[2])
        if klr[0] >= len(q):
            heapq.heappush(q, (pr, klr))
    for pr, klr in q:
        ans += max(klr[1], klr[2])
    return ans
              
              
def solve():  
    N = int(input())
    KLR = []  
    for _ in range(N):
        klr = list(map(int, input().split()))
        klr[0] -= 1 # convert to 0-based index to avoid confusion                                                                                                                                           
        KLR.append(klr)
    ans = 0   
    KLR_L = []
    KLR_R = []
    for klr in KLR:
        if klr[1] > klr[2]:
            KLR_L.append(klr)
        elif klr[1] < klr[2]:
            klr[0] = N-1-klr[0]-1
            if klr[0] < 0:
                ans += min(klr[1], klr[2])
            else:
                KLR_R.append(klr)
        else: 
            ans += klr[1]
    KLR_L.sort(key=lambda klr: klr[0])
    KLR_R.sort(key=lambda klr: klr[0])
    ans += process(KLR_L)
    ans += process(KLR_R)
    print(ans)
              
T = int(input())
              
for _ in range(T):
    solve()