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:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    T=I()
    import heapq
    
    def calc(X):
        #厳しいところから見ていき，大きいものから入れていく
        hq=[]
        heapq.heapify(hq)
        X.sort(reverse=True)#厳しい順に
        N2=len(X)
        cur=0
        temp=0
        for i in range(N2-1,-1,-1):
            while cur<=N2-1:
                k=X[cur][0]
                if k>i:
                    heapq.heappush(hq,-1*X[cur][1])
                    cur+=1
                else:
                    break
            if len(hq)!=0:
                a=heapq.heappop(hq)
                temp+=-1*a
                
        #print(X,temp)
        return temp 
    
    
    for _ in range(T):
        # 左右それぞれどちらにいきたいかで分けていくことで問題を独立に
        N=I()
        ans=0
        L=[]
        R=[]
        for i in range(N):
            K,l,r=MI()
            if l>=r:
                ans+=r
                L.append((K,l-r))#左からK以内なら+l-r点
            else:
                ans+=l
                R.append((N-K,r-l))#右からN-K以内なら+r-l点
                
        ans+=calc(L)
        ans+=calc(R)
        print(ans)
        
        
        

main()

Submission status: Accepted

Solution code:
from bisect import *
from collections import defaultdict
def solve():
  T = int(input())
  ans = [0]*T
  for t in range(T):
    N = int(input())
    left = defaultdict(lambda: [])
    right = defaultdict(lambda: [])
    for i in range(N):
      k,l,r = map(int, input().split())
      if k==N:
        ans[t] += l
      else:
        if l>r:
          insort_right(left[k],l-r)
        elif l<r:
          insort_right(right[k+1],r-l)
        ans[t] += min(l,r)
    lis = []
    for i in range(N,0,-1):
      for l in left[i]:
        insort_right(lis,l)
      if len(lis):
        ans[t] += lis.pop(-1)
    lis = []
    for i in range(2,N+1):
      for r in right[i]:
        insort_right(lis,r)
      if len(lis):
        ans[t] += lis.pop(-1)
  return ans
print(*solve(),sep='\n')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *
from heapq import *

for _ in range(int(input())):
    N = int(input())
    ans = 0
    dl = defaultdict(list)
    dr = defaultdict(list)
    
    for _ in range(N):
        K, L, R = map(int, input().split())
        m = min(L, R)
        ans += m
        
        if L==m:
            dr[K+1].append(R-m)
        else:
            dl[K].append(L-m)
        
    pq = []
    
    for i in range(N, 0, -1):
        for v in dl[i]:
            heappush(pq, -v)
        
        if len(pq)>0:
            ans += -heappop(pq)
    
    pq = []
    
    for i in range(1, N+1):
        for v in dr[i]:
            heappush(pq, -v)
        
        if len(pq)>0:
            ans += -heappop(pq)
    
    print(ans)

Submission status: Accepted

Solution code:
import heapq
def solve():
  N = int(input())
  ans = 0
  left,right = [ [] for i in range(N) ],[ [] for i in range(N) ]
  for _ in range(N):
    k,l,r = map(int,input().split())
    ans += min(l,r)
    if l>r:
      left[k-1].append(l-r)
    else:
      if k >= N: continue
      right[k].append(r-l)

  # left
  pq = []
  for i in range(N-1,-1,-1):
    for l in left[i]:
      heapq.heappush(pq,-l)
    if pq:
      ans += -heapq.heappop(pq)

  # right
  pq = []
  for i in range(N):
    for r in right[i]:
      heapq.heappush(pq,-r)
    if pq:
      ans += -heapq.heappop(pq)

  print(ans)

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

Submission status: Accepted

Solution code:
import sys
import heapq
def input(): return sys.stdin.readline().rstrip()

def culc(li):
    li.sort(key=lambda x: x[1])
    h=[]
    for i in li:
        if len(h) >= i[1]:
            heapq.heappushpop(h, i[0])
        else:
            heapq.heappush(h, i[0])
    return sum(h)

def main():
    T=int(input())
    for _ in range(T):
        n=int(input())
        mae=[]
        ushiro=[]
        kijun=0
        for _ in range(n):
            k,l,r=map(int, input().split())
            if l>r:
                mae.append([l-r,k])
            else:
                ushiro.append([r-l,n-k])
            kijun+=min(l,r)
        print(culc(mae)+culc(ushiro)+kijun)
                    



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
Ncase = int(input())
for case in range(Ncase):
  N = int(input())
  ans = 0
  Left = [];Right = []
  for i in range(N):
    K,L,R = map(int,input().split())
    if L > R:
      Left.append((K-1,L-R))
      ans += R
    elif R > L:
      if K != N: #K=Nの時はどこにおいても左と判定される。
        Right.append((N-1-K,R-L))
      ans += L
    else:
      ans += L
  Left.sort(reverse=True);Right.sort(reverse=True) #Kの小さい順、左にいたときのプラス分が大きい順に並んだ
  #print(Left,Right)
  now = 0
  PQ = []
  for loc in reversed(range(N)):
    #print(now,Left[now][0],loc)
    while now < len(Left) and Left[now][0] == loc:
      heappush(PQ,-Left[now][1])
      now += 1
      if now >= len(Left):
        break
    if PQ:
      plus = -heappop(PQ)
      ans += plus
  
  now = 0
  PQ = []
  for loc in reversed(range(N)):
    while now < len(Right) and Right[now][0] == loc:
      heappush(PQ,-Right[now][1])
      now += 1
      if now >= len(Right):
        break
    if PQ:
      plus = -heappop(PQ)
      ans += plus
  print(ans)

Submission status: Accepted

Solution code:
#写経
#https://atcoder.jp/contests/aising2020/submissions/15195468
from heapq import heappop, heappush
import sys
input = sys.stdin.readline

def resolve():
    T = int(input())
    for _ in range(T):
        N = int(input())
        ans = 0
        camels0 = [[] for _ in range (N)]
        camels1 = [[] for _ in range (N)]
        for _ in range(N):
            K,L,R = map(int, input().split())
            if L>R:
                camels0[K-1].append(L-R)
            elif L<R and K<N:
                camels1[N-K-1].append(R-L)
            ans += min(L,R)
        
        H = []
        for i in range(N):
            for j in camels0[i]:
                heappush(H,j)
            while len(H) > i+1:
                heappop(H)
        ans += sum(H)
        H = []
        for i in range(N):
            for j in camels1[i]:
                heappush(H,j)
            while len(H) > i+1:
                heappop(H)
        ans += sum(H)
        print(ans)
resolve()

Submission status: Accepted

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 = [[]for _ in range(n)]
    right = [[]for _ in range(n)]
    score = 0
    for K,L,R in klr:
        if K!=n:
            if L<R:
                score+=L
                right[n-K-1].append(R-L)
            elif R<L:
                score+=R
                left[K-1].append(L-R)
            else:
                score+=L
        else:
            score+=L
    
    def calc(ls):
        n = len(ls)
        use = []
        retval = 0
        for i in reversed(range(n)):
            for x in ls[i]:
                heapq.heappush(use, -x)
            if use:
                retval-=heapq.heappop(use)
        return retval
    score+=calc(left)
    score+=calc(right)
    print(score)

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush


T = int(input())
for t in range(T):
    N = int(input())
    left, right = [], []
    ans = 0
    for i in range(N):
        K, L, R = map(int, sys.stdin.readline().split())
        if L > R:
            ans += L
            left.append((K, L - R))
        elif L < R:
            ans += R
            right.append((K, R - L))
        else:
            ans += L
    # left
    pool = []
    pos = 1
    left.sort()
    cur = 0
    while cur < len(left):
        while cur < len(left) and left[cur][0] == pos:
            k, d = left[cur]
            heappush(pool, d)
            cur += 1
        while len(pool) > pos:
            d = heappop(pool)
            ans -= d
        pos += 1
            
    # right
    pool = []
    pos = N
    right.sort(reverse=True)
    cur = 0
    while cur < len(right):
        while cur < len(right) and right[cur][0] == pos:
            k, d = right[cur]
            heappush(pool, d)
            cur += 1
        while len(pool) > N - pos:
            d = heappop(pool)
            ans -= d
        pos -= 1

    print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush

ans_l = []
T = int(input())
for t in range(T):
    N = int(input())
    left, right = [], []
    ans = 0
    for i in range(N):
        K, L, R = map(int, sys.stdin.readline().split())
        if L > R:
            ans += L
            left.append((K, L - R))
        elif L < R:
            ans += R
            right.append((K, R - L))
        else:
            ans += L
    # left
    pool = []
    pos = 1
    left.sort()
    cur = 0
    while cur < len(left):
        while cur < len(left) and left[cur][0] == pos:
            k, d = left[cur]
            heappush(pool, d)
            cur += 1
        while len(pool) > pos:
            d = heappop(pool)
            ans -= d
        pos += 1
            
    # right
    pool = []
    pos = N
    right.sort(reverse=True)
    cur = 0
    while cur < len(right):
        while cur < len(right) and right[cur][0] == pos:
            k, d = right[cur]
            heappush(pool, d)
            cur += 1
        while len(pool) > N - pos:
            d = heappop(pool)
            ans -= d
        pos -= 1

    ans_l.append(ans)


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

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush

ans_l = []
T = int(input())
for t in range(T):
    ans = 0
    N = int(input())
    left = []
    right = []
    neutral = []
    for i in range(N):
        K, L, R = map(int, sys.stdin.readline().split())
        if L > R:
            heappush(left, (K, L - R, L, R))
        elif L < R:
            heappush(right, (-K, R - L, L, R))
        else:
            ans += L
    # left
    pool = []
    pos = 1
    while left:
        while left and left[0][0] == pos:
            k, d, l, r = heappop(left)
            heappush(pool, (d, l, r))
        while len(pool) > pos:
            d, l, r = heappop(pool)
            ans += r
        pos += 1
    while pool:
        d, l, r = heappop(pool)
        ans += l
            
    # right
    pool = []
    pos = N
    while right:
        while right and right[0][0] == -pos:
            k, d, l, r = heappop(right)
            heappush(pool, (d, l, r))
        while len(pool) > N - pos:
            d, l, r = heappop(pool)
            ans += l
        pos -= 1
    while pool:
        d, l, r = heappop(pool)
        ans += r

    ans_l.append(ans)


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

Submission status: Accepted

Solution code:
import heapq

def g(LS):
    Q = [];
    QLen = 0
    SC = 0

    for k,sc in sorted(LS):
        heapq.heappush(Q, sc)
        QLen += 1
        SC += sc

        if  QLen > k:
            SC -= heapq.heappop(Q)
            QLen -= 1

    return SC
            


def f():
    N = int(input())
    LS = []
    RS = []
    SC0 = 0

    for _ in range(N):
        K,L,R = map(int, input().split())
        SC = abs(L - R)
        SC0 += min(L, R)

        if L >= R:
            LS.append((K, SC))
        else:
            RS.append((N-K, SC))

    
    print(SC0 + g(LS) + g(RS))


T = int(input())
for _ in range(T):
    f()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
it = lambda: list(map(int, input().strip().split()))


def greedy(A):
    ans = 0
    A.sort(key=lambda x:x[0])
    pq = []
    for k, a, b in A:
        ans += a
        heappush(pq, [a - b, k, a, b])
        while len(pq) > k:
            ans -= heappop(pq)[0]
    return ans


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

    prefer_late = []
    prefer_early = []
    for _ in range(N):
        k, a, b = it()
        if a >= b:
            prefer_early.append([k, a, b])
        else:
            prefer_late.append([N - k, b, a])
    
    ans = 0
    ans += greedy(prefer_early)
    ans += greedy(prefer_late)
    print(ans)


T = int(input())
for _ in range(T):
    solve()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify
from collections import deque

T = int(input())

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

    pos = []
    neg = []

    for i in range(N):
        k, l, r = camel[i]
        if l - r >= 0:
            pos.append((r - l, k, i))
        else:
            neg.append((l - r, N - k, i))

    pos.sort(key=lambda x:x[1], reverse=True)
    p = len(pos)

    heappos = []
    respos = [None for i in range(N)]

    j = 0
    for i in range(N)[::-1]:
        while j < p and pos[j][1] == i + 1:
            heappush(heappos, pos[j])
            j += 1
        if heappos:
            d, k, id = heappop(heappos)
            respos[i] = id
    for i in range(N)[::-1]:
        if respos[i] is None and heappos:
            d, k, id = heappop(heappos)
            respos[i] = id


    neg.sort(key=lambda x:x[1], reverse=True)
    n = len(neg)

    heapneg = []
    resneg = [None for i in range(N)]

    j = 0
    for i in range(N)[::-1]:
        while j < n and neg[j][1] == i + 1:
            heappush(heapneg, neg[j])
            j += 1
        if heapneg:
            d, k, id = heappop(heapneg)
            resneg[i] = id
    while j < n:
        heappush(heapneg, neg[j])
        j += 1
    for i in range(N)[::-1]:
        if resneg[i] is None and heapneg:
            d, k, id = heappop(heapneg)
            resneg[i] = id

    respos = [respos[i] for i in range(N) if respos[i] is not None]
    resneg = [resneg[i] for i in range(N) if resneg[i] is not None]
    res = respos + resneg[::-1]

    ans = 0

    for i in range(N):
        k, l, r = camel[res[i]]
        if k >= i + 1:
            ans += l
        else:
            ans += r

    print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import *
def input(): return sys.stdin.readline().strip()


def func(left):
    ll = len(left)
    """
    前から順番に詰めていく方式だと次の反例が存在する：
    ll = 2, left = [(1, 1), (2, 2), (3, 100)]
    (3, 100)をなるべく先頭に置くべきだが、前のコードだと３番目が車で保留。
    ll < 3なのでその時は訪れない。

    なのでやはり後ろから攻めるしかない模様。
    """
    L = [[] for _ in range(ll + 1)]
    for k, v in left:
        if k > ll: k = ll
        L[k].append(v)
    ans = 0
    q = []
    for i in range(ll, 0, -1):
        for v in L[i]: heappush(q, -v)
        if q: ans -= heappop(q)
    return ans


def main():
    T = int(input())
    for _ in range(T):
        n = int(input())
        ans = 0
        left = []
        right = []
        for _ in range(n):
            k, l, r = map(int, input().split())
            if l > r:
                ans += r
                left.append((k, l - r))
            else:
                ans += l
                right.append((n - k, r - l))
        #print("left={}".format(left))
        #print("right={}".format(right))
        ans += func(left)
        ans += func(right)
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
T=int(input())

for _ in range(T):
  N=int(input())
  
  llist=[]
  rlist=[]
  base=0
  for _ in range(N):
    K,L,R=map(int,input().split())    
    if L>R:
      llist.append((K,L-R))
      base+=R
    elif L<R:
      rlist.append((N-K,R-L))
      base+=L
    else:
      base+=L
      
  llist.sort()
  rlist.sort()      
  #print(base)
  #print(llist)
  #print(rlist)
  
  hq_left=[]
  for i,l in llist:
    heapq.heappush(hq_left,l)
    if len(hq_left)>i:
      heapq.heappop(hq_left)
  hq_right=[]
  for i,r in rlist:
    heapq.heappush(hq_right,r)
    if len(hq_right)>i:
      heapq.heappop(hq_right)
      
  answer=base
  while hq_left:
    answer+=heapq.heappop(hq_left)
  while hq_right:
    answer+=heapq.heappop(hq_right)
    
  print(answer)

Submission status: Accepted

Solution code:
import heapq
T=int(input())

for _ in range(T):
  N=int(input())
  
  llist=[]
  rlist=[]
  base=0
  for _ in range(N):
    K,L,R=map(int,input().split())
    base+=min(L,R)
    if L>R:
      llist.append((K,L-R))
    elif L<R:
      rlist.append((N-K,R-L))
      
  llist.sort()
  rlist.sort()      
  #print(base)
  #print(llist)
  #print(rlist)
  
  hq_left=[]
  for i,l in llist:
    heapq.heappush(hq_left,l)
    if len(hq_left)>i:
      heapq.heappop(hq_left)
  hq_right=[]
  for i,r in rlist:
    heapq.heappush(hq_right,r)
    if len(hq_right)>i:
      heapq.heappop(hq_right)
      
  answer=base
  while hq_left:
    answer+=heapq.heappop(hq_left)
  while hq_right:
    answer+=heapq.heappop(hq_right)
    
  print(answer)

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
def solve(n,klr):
  kk=[(-1,-1)]
  for k,l,r in klr:kk.append((k-1,r-l))
  kk.sort()
  h=[]
  ans=0
  for i in range(n-1,-1,-1):
    while kk[-1][0]>=i:heappush(h,kk.pop()[1])
    if len(h):ans-=heappop(h)
  return ans

for _ in range(int(input())):
  n=int(input())
  klr=[list(map(int,input().split()))for _ in range(n)]
  pk=[]
  mk=[]
  ans=0
  for i in range(n):
    k,l,r=klr[i]
    ans+=min(l,r)
    if l>=r:pk.append(i)
    else:mk.append(i)
  l=len(pk)
  for i in mk:
    klr[i][0]=n-klr[i][0]
    klr[i][1],klr[i][2]=klr[i][2],klr[i][1]
  ans+=solve(len(pk),[klr[i]for i in pk])+solve(len(mk),[klr[i]for i in mk])
  print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import *
readline = sys.stdin.readline

def solve2(left):
    if len(left) == 0:
        return 0
    ans = 0
    k2values = {}
    for v, k in left:
        if k not in k2values:
            k2values[k] = []
        k2values[k].append(v)
    
    pq = []
    maxk = max(k for v,k in left)
    for k in range(maxk, 0, -1):
        if k in k2values:
            for v in k2values[k]:
                heappush(pq, -v)
        if len(pq) > 0:
            v = heappop(pq)
            ans += -v
    return ans


def solve():
    N = int(readline())
    
    left = []
    right = []
    
    ans = 0
    
    for i in range(N):
        k, l, r = map(int, readline().split())
        if l > r:
            left.append((l - r, k))
            ans += r
        else:
            right.append((r - l, N - k))
            ans += l
    
    ans += solve2(left)
    ans += solve2(right)
    
    print(ans)

T = int(readline())
for i in range(T):
    solve()

Submission status: Accepted

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

T = int(input())
anss = []
for _ in range(T):
    N = int(input())
    Ls = defaultdict(list)
    Rs = defaultdict(list)
    ans = 0
    for i in range(N):
        K, L, R = map(int, input().split())
        if L > R:
            Ls[K].append(L-R)
            ans += R
        elif L < R:
            Rs[N-K].append(R-L)
            ans += L
        else:
            ans += L

    def f(Ls):
        PQL = []
        for j in range(1, N+1):
            for L in Ls[j]:
                heappush(PQL, L)
            while len(PQL) > j:
                heappop(PQL)
        return sum(PQL)

    ans += f(Ls)
    ans += f(Rs)

    anss.append(ans)

print('\n'.join(map(str, anss)))

Submission status: Accepted

Solution code:
t=int(input())
import heapq
for _ in range(t):
    n=int(input())
    L=[];R=[]
    ans=0
    for _ in range(n):
        ki,li,ri = map(int, input().split())
        dif=li-ri
        if dif>=0:
            L.append((ki-1,dif))
            ans+=ri
        else:
            R.append((n-ki-1,-dif))
            ans+=li
    L.sort();R.sort()
    hL=[]
    hR=[]
    for i in range(len(L)):
        if L[i][0]>=len(hL):
            heapq.heappush(hL,L[i][1])
        elif L[i][0]==len(hL)-1:
            heapq.heappushpop(hL,L[i][1])
    for i in range(len(R)):
        if R[i][0]>=len(hR):
            heapq.heappush(hR,R[i][1])
        elif R[i][0]==len(hR)-1:
            heapq.heappushpop(hR,R[i][1])
    print(ans+sum(hL)+sum(hR))

Submission status: Accepted

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)


def solve(N, t):
    d1 = array2(N, 0)
    d2 = array2(N, 0)

    t  = [(x[0]-1, x[1], x[2]) for x in t]
    t1 = [(x[0], x[1] - x[2]) for x in t if x[1] >= x[2]]
    t2 = [(N - 2 - x[0], x[2] - x[1]) for x in t if x[1] < x[2] and N - 2 - x[0] >= 0]

    ans = sum([min(x[1], x[2]) for x in t])
    
    for k, dt in t1:
        d1[k].append(dt)

    S = []

    for i in range(N):
        for dt in d1[i]:
            insort(S, dt)

        if len(S) > i:
            S = S[len(S)-i-1:]

    #print("d1: ", d1, " S: ", S)

    ans += sum(S)

    for k, dt in t2:
        d2[k].append(dt)

    S = []
    for i in range(N):
        for dt in d2[i]:
            insort(S, dt)

        if len(S) > i:        
            S = S[len(S)-i-1:]

    #print("d2: ", d2, " S: ", S)
    ans += sum(S)
    print(ans)

T = n1()

for _ in range(T):
    N = n1()
    t = nm(N)
    solve(N, t)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from heapq import heappop,heappush
t=int(input())
for _ in range(t):
	happy=0
	n=int(input())
	camel=[]
	p=[]
	m=[]
	for i in range(n):
		k,l,r=map(int,input().split())
		happy+=min(l,r)
		if l-r>=0:
			p.append((k,l-r))
		else:
			m.append((k,r-l))
	p.sort();m.sort(reverse=True)
	now=0
	P=[];M=[]
	for i in range(n):
		if now<len(p):
			while p[now][0]==i+1:
				heappush(P,(p[now][1],p[now][0]))
				now+=1
				if now==len(p):
					break
		while len(P)>i+1:
			r=heappop(P)
	now=0
	for i in range(n,0,-1):
		if now<len(m):
			while m[now][0]==i:
				heappush(M,(m[now][1],m[now][0]))
				now+=1
				if now==len(m):
					break
		while len(M)>n-i:
			r=heappop(M)
	for x in P:
		happy+=x[0]
	for x in M:
		happy+=x[0]
	print(happy)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
import math

def solve():
    N = int(sysread())
    KLR_left, KLR_right = [], []
    counts_l, counts_r = [0] * (N+1), [0] * (N+1)

    for _ in range(N):
        k,l,r = map(int, sysread().split())
        if l>r:
            KLR_left.append((k, l, r))
            counts_l[k] += 1
        else:
            KLR_right.append((k, l, r))
            counts_r[k] += 1

    KLR_left = sorted(KLR_left, key = lambda x:x[0], reverse=True)
    KLR_right = sorted(KLR_right, key=lambda x:x[0])
    queue_left = []
    queue_right = []
    dump = []
    SUM = 0
    for i in range(1, N+1):
        for j in range(counts_l[i]):
            k, l, r = KLR_left.pop()
            heappush(queue_left, (l-r, l, r))
            SUM += l

        while True:
            if len(queue_left)>i:
                l_r, l, r = heappop(queue_left)
                dump.append((l_r, l, r))
                SUM -= l_r
            else:break


    #print(filled_left)
    for i in list(range(1, N+1))[::-1]:
        for j in range(counts_r[i]):
            k, l, r = KLR_right.pop()
            heappush(queue_right, (r-l, l, r))
            SUM += r
        while True:
            if len(queue_right) > N-i:
                try:
                    r_l, l, r = heappop(queue_right)
                except:break
                dump.append((r_l, l, r))
                SUM -= r_l
            else:break
    return SUM

def run():
    T = int(sysread())
    for i in range(T):
        print(solve())



if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
import heapq
T=int(input())
for _ in range(T):
  ans=0
  N=int(input())
  Ls=[[] for _ in range(N)]
  #RsはK=Nのとき、達成不可。
  Rs=[[] for _ in range(N)]
  for _ in range(N):
    K,L,R=map(int,input().split())
    ans+=max(L,R)
    if L>R:
      Ls[K-1].append(L-R)
    if L<R:
      if K==N:
        ans-=R-L
        continue
      Rs[N-K].append(R-L)
  #先に左から
  dat=[]
  heapq.heapify(dat)
  for i in range(N):
    if not Ls[i]:
      continue
    for l in Ls[i]:
      heapq.heappush(dat,l)
    while len(dat)>i+1:
      ans-=heapq.heappop(dat)
  #次に右を
  dat=[]
  heapq.heapify(dat)
  for i in range(1,N):
    if not Rs[i]:
      continue
    for l in Rs[i]:
      heapq.heappush(dat,l)
    while len(dat)>i:
      ans-=heapq.heappop(dat)
  print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush
def main():
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    l_camel = [[] for _ in range(n)]
    r_camel = [[] for _ in range(n)]
    ans = 0
    for _ in range(n):
        k, l, r = map(int, input().split())
        if l >= r:
            ans += r
            l_camel[k-1].append(l-r)
        else:
            ans += l
            r_camel[~(k-1)].append(r-l)
    
    cur = 0
    que = []
    for i in range(n):
        for el in l_camel[i]:
            heappush(que, el)
        while len(que) > i+1:
            heappop(que)
    ans += sum(que)

    que = []
    for i in range(n):
        for el in r_camel[i]:
            heappush(que, el)
        while len(que) > i:
            heappop(que)
    ans += sum(que)
    print(ans)


if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        main()

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify

def f(p):
  res = 0
  s = len(p)
  for i in range(s):
    if p[i][0] > s:
      p[i][0] = s
  p.sort(reverse = True)
  hq = []
  idx = 0
  for i in range(s,0,-1):
    #print('p:',p,'i:',i)
    while(idx < s and p[idx][0] == i):
      heappush(hq,-p[idx][1])
      idx += 1
    #print('hq:',hq)
    if len(hq) > 0:
      res -= heappop(hq)
      #print('res:',res)
  return res

def solve():
  n = int(input())
  pl = []
  pr = []
  ans = 0
  for i in range(n):
    k,l,r = map(int,input().split())
    m = min(l,r)
    l -= m
    r -= m
    ans += m
    if l > 0:
      pl.append([k,l])
    else:
      pr.append([n-k,r])
  #print('pl:',pl,'pr:',pr,'ans:',ans)
  ans += f(pl)
  ans += f(pr)
  print(ans)

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

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
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)

Submission status: Accepted

Solution code:
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)