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


class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s

    def bisect_left(self, w):
        # condition : always all element is not minus
        # return minimum idx where bit.sum(idx) >= w
        if w <= 0:
            return 0
        idx = 0  # self.bit[idx] < w
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] < w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1


t = int(input())
for _ in range(t):
    n = int(input())
    camels = [tuple(map(int, input().split())) for _ in range(n)]
    camels.sort(key=lambda x: abs(x[1] - x[2]) if x[0] < n else 0,
                reverse=True)

    # print()
    # print('-' * 10)
    # print(*camels, sep='\n')

    bit = BIT1(n)
    ans = 0
    for i in range(1, n + 1):
        bit.add(i, 1)

    for k, l, r in camels:
        s = bit.sum(k)
        if k == n:
            # lを使うしかない
            idx = bit.bisect_left(s)
            bit.add(idx, -1)
            ans += l
        else:
            if l > r:
                if s == 0:
                    # lを使えない
                    idx = bit.bisect_left(s + 1)
                    bit.add(idx, -1)
                    ans += r
                else:
                    idx = bit.bisect_left(s)
                    bit.add(idx, -1)
                    ans += l
            elif r > l:
                s2 = bit.sum(n)
                if s2 - s == 0:
                    # rを使えない
                    idx = bit.bisect_left(s)
                    bit.add(idx, -1)
                    ans += l
                else:
                    idx = bit.bisect_left(s + 1)
                    bit.add(idx, -1)
                    ans += r
            else:
                # l == r
                # どっちでもいい
                ans += l

    print(ans)

Submission status: Wrong Answer

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

t = int(input()[:-1])

for loop in range(t):
    n = int(input()[:-1])
    lg = []
    rg = []
    for i in range(n):
        k,l,r = map(int,input()[:-1].split())
        if l > r:
            lg.append([k,l,r])
        else:
            rg.append([n-k+1,l,r])
    lg.sort(key=lambda x:(x[0],-x[1]))
    rg.sort(key=lambda x:(x[0],-x[2]))
    fill = 0
    ans = 0
    for l in lg:
        if l[0] > fill:
            fill += 1
            ans += l[1]
        else:
            fill += 1
            ans += l[2]
    fill = 0
    for r in rg:
        if r[0] > fill:
            fill += 1
            ans += r[2]
        else:
            fill += 1
            ans += r[1]
    # print(lg)
    # print(rg)
    print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
t = int(input())
for _ in range(t):
    n = int(input())
    lis = [[] for _ in range(n+1)]
    s = 0
    for _ in range(n):
        k, l, r = map(int, input().split())
        s += l
        lis[k].append((l, r))
    que = []
    for i in range(n):
        for l, r in lis[i]:
            if r - l > 0:
                heappush(que, l-r)
        if len(que) > 0:
            x = heappop(que)
            s -= x

    print(s)

Submission status: Wrong Answer

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

t = int(input()[:-1])

for loop in range(t):
    n = int(input()[:-1])
    lg = []
    rg = []
    for i in range(n):
        k,l,r = map(int,input()[:-1].split())
        if l > r:
            lg.append([k,l,r])
        else:
            rg.append([n-k,l,r])
    lg.sort(key=lambda x:(x[0],-x[1]))
    rg.sort(key=lambda x:(x[0],-x[2]))
    fill = 0
    ans = 0
    for l in lg:
        if l[0] > fill:
            fill += 1
            ans += l[1]
        else:
            fill += 1
            ans += l[2]
    fill = 0
    for r in rg:
        if r[0] > fill:
            fill += 1
            ans += r[2]
        else:
            fill += 1
            ans += r[1]
    # print(lg)
    # print(rg)
    print(ans)

Submission status: Wrong Answer

Solution code:
T = int(input())
for _ in range(T):
   N = int(input())
   left, right = [], []
   for _ in range(N):
      k,l,r = map(int, input().split())
      if l > r:
         left.append((k-1,l,r))
      else:
         right.append((N-k,l,r))
   left = sorted(left, key=lambda x: x[0])
   right = sorted(right, key=lambda x: x[0])
   # print(left, right)
   ans = 0
   for i,(k,l,r) in enumerate(left):
      ans += l if i <= k else r
   for i,(k,l,r) in enumerate(right):
      ans += r if i < k else l
   print(ans)

Submission status: Wrong Answer

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def f(x, y, z):
    return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    T = ii()

    for t in range(T):
        N = ii()
        ims = [0] * N
        for n in range(N):
            K, L, R = il()
            ims[0] += L
            if K == N: continue
            ims[K] += R - L
        print(max(list(itertools.accumulate(ims))))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from random import random


class TreapNode:
    """Treapのノード定義
    メンバ変数: 値、優先度、親へのポインタ、左右の子へのポインタ"""
    def __init__(self, val):
        self.val = val
        self.priority = random()
        self.parent, self.right, self.left = None, None, None


class Treap:
    """平衡二分探索木: 値の検索、挿入、削除などクエリ処理をO(logN)で実行する"""
    def __init__(self, is_multiset=False):
        self.is_multiset = is_multiset
        self.root = None

    def search(self, val: int) -> bool:
        """値の検索: 集合に値valを持つノードが存在するか"""
        ptr = self.root
        while ptr is not None:
            if val < ptr.val:
                ptr = ptr.left
            elif val > ptr.val:
                ptr = ptr.right
            else:
                return True
        return False

    def insert(self, val: int) -> bool:
        """値の削除: 集合に値valを持つノードを挿入する"""
        if self.root is None:
            self.root = TreapNode(val)
            return True

        # ノードの挿入
        ptr = self.root 
        while True:
            if val < ptr.val:
                if ptr.left is None:
                    ptr.left = TreapNode(val)
                    ptr.left.parent = ptr
                    ptr = ptr.left
                    break
                ptr = ptr.left
            else:
                if val == ptr.val and not self.is_multiset:
                    return False
                elif ptr.right is None:
                    ptr.right = TreapNode(val)
                    ptr.right.parent = ptr
                    ptr = ptr.right
                    break
                ptr = ptr.right

        # 木の回転によってヒープ性を保つ
        while (ptr.parent is not None) and (ptr.parent.priority > ptr.priority):
            if ptr.parent.right == ptr:
                self._rotate_left(ptr.parent)
            else:
                self._rotate_right(ptr.parent)
        if ptr.parent is None:
            self.root = ptr 

    def delete(self, val: int) -> True:
        """値の削除: 集合から値valを持つノードを削除する"""
        if self.root is None:
            return False
 
        ptr = self.root   
        tmp = None
        while ptr is not None: 
            if val < ptr.val:
                ptr = ptr.left
            elif val > ptr.val:
                ptr = ptr.right
            else:
                tmp = ptr
                if (ptr.right is not None) and ptr.right.val == val:
                    ptr = ptr.right
                elif (ptr.left is not None) and ptr.left.val == val:
                    ptr = ptr.left
                else:
                    break
        ptr = tmp
        # 木の回転によって削除したいノードを葉に持っていく
        while (ptr.left is not None) or (ptr.right is not None):
            if ptr.left is None:
                self._rotate_left(ptr)
            elif ptr.right is None:
                self._rotate_right(ptr)
            elif ptr.left.priority < ptr.right.priority:
                self._rotate_right(ptr)
            else:
                self._rotate_left(ptr)
            if self.root == ptr:
                self.root = ptr.parent
 
        # ノードの削除
        if ptr.left is None and ptr.right is None:
            if ptr == self.root:
                self.root = None
            elif ptr.parent.left == ptr:
                ptr.parent.left = None
            else:
                ptr.parent.right = None      
        return True

    def _rotate_left(self, ptr):
        """木の左回転を行う"""
        w = ptr.right
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.left == ptr:
                w.parent.left = w
            else:
                w.parent.right = w
        ptr.right = w.left
        if ptr.right is not None:
            ptr.right.parent = ptr
        ptr.parent = w
        w.left = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None

    def _rotate_right(self, ptr):
        """木の右回転を行う"""
        w = ptr.left
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.right == ptr:
                w.parent.right = w
            else:
                w.parent.left = w
        ptr.left = w.right
        if ptr.left is not None:
            ptr.left.parent = ptr
        ptr.parent = w
        w.right = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None

    def search_min(self):
        ptr = self.root
        ret = None
        while ptr is not None:
            ret = ptr.val
            ptr = ptr.left
        return ret

    def search_max(self):
        ptr = self.root
        ret = None
        while ptr is not None:
            ret = ptr.val
            ptr = ptr.right
        return ret

    def search_le(self, val: int):
        """val以下の最大の値を探す"""
        ptr = self.root
        ret = None
        while ptr is not None:
            if ptr.val <= val:
                ret = ptr.val
                ptr = ptr.right
            else:
                ptr = ptr.left
        return ret

    def search_lt(self, val: int):
        """valよりも小さいの最大の値を探す"""
        ptr = self.root
        ret = None
        while ptr is not None:
            if ptr.val < val:
                ret = ptr.val
                ptr = ptr.right
            else:
                ptr = ptr.left
        return ret

    def search_ge(self, val: int):
        """val以上の最小の値を探す"""
        ptr = self.root
        ret = None
        while ptr is not None:
            if ptr.val >= val:
                ret = ptr.val
                ptr = ptr.left
            else:
                ptr = ptr.right
        return ret
      
    def search_gt(self, val: int):
        """valよりも大きい最小の値を探す"""
        ptr = self.root
        ret = None
        while ptr is not None:
            if ptr.val > val:
                ret = ptr.val
                ptr = ptr.left
            else:
                ptr = ptr.right
        return ret


t = int(input())
for _ in range(t):
    n = int(input())
    info = [list(map(int, input().split())) for i in range(n)]
    li = []
    ans = 0
    p_cnt = 0
    m_cnt = 0
    for k, l, r in info:
        diff = l - r
        ans += r
        if diff > 0:
           p_cnt += 1
        if diff < 0:
           m_cnt += 1
        li.append((diff, k - 1))
        li = sorted(li, reverse=True)

    tp1 = Treap()
    tp2 = Treap()
    

    for i in range(p_cnt):
        tp1.insert(i)
    for i in range(n - m_cnt, n):
        tp2.insert(i)

    for diff, k in li:
        if diff > 0:
            ind = tp1.search_le(k)
            if ind is None:
                continue
            if ind <= k:
                tp1.delete(ind)
                ans += diff
        elif diff == 0:
            continue
        else:
            ind = tp2.search_gt(k)
            if ind is not None:
                tp2.delete(ind)
            else:
                ans += diff
    print(ans)

Submission status: Wrong Answer

Solution code:
t=int(input())
for i in range(t):
  n=int(input())
  klr = [list(map(int,input().split())) for i in range(n)]
  klr.sort(key=lambda x:x[0])
  l=1
  r=n
  ans=list()
  for j in range(n):
    if klr[j][1] >= klr[j][2]:
      if l <= klr[j][0]:
        l+=1
        ans.append(klr[j][1])
      else:
        r-=1
        ans.append(klr[j][2])
    elif r > klr[j][0]:
      r-=1
      ans.append(klr[j][2])
    else:
      l+=1
      ans.append(klr[j][1])
  print(sum(ans))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint
from copy import deepcopy


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def interval_sum(self, i, j): # i <= x < j の区間
        return self.sum(j - 1) - self.sum(i - 1) if i else self.sum(j - 1)

    def search_r(self, l, r):
        #右側にだんだん伸ばしていく
        # l <= x < r
        ng = l - 1
        ok = r - 1
        while ng + 1 < ok:
            mid = (ng + ok) // 2
            if self.interval_sum(l, mid + 1):
                ok = mid
            else:
                ng = mid
        return ok

    def search_l(self, l, r):
        #左側にだんだん伸ばしていく
        # l <= x < r
        ng = r
        ok = l
        while ok + 1 < ng:
            mid = (ok + ng) // 2
            if self.interval_sum(mid, ng):
                ok = mid
            else:
                ng = mid
        return ok

t = I()
for _ in range(t):
    n = I()
    ans = 0
    L = []
    K = []
    for _ in range(n):
        k, l, r = LI()
        diff = l - r
        if diff > 0:
            L += [(diff, k, 1)]
        elif diff < 0:
            L += [(-diff, k, 0)]
        ans += min(l, r)

    L.sort()
    bit = BIT(n)
    for j in range(n):
        bit.add(j, 1)
    for d, ki, flg in L:
        if flg:
            if bit.interval_sum(0, ki):
                idx = bit.search_l(0, ki)
                bit.add(idx, -1)
                ans += d
        else:
            if bit.interval_sum(ki, n):
                idx = bit.search_r(ki - 1, n)
                bit.add(idx, -1)
                ans += d
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import*
input=sys.stdin.buffer.readline
def solve():
    n=int(input())
    c=sorted([[*map(int,input().split())]for _ in range(n)],
    key=lambda x:x[0] if x[1]>x[2]else x[0]+n)
    m=0
    h=[]
    for i,(k,l,r)in enumerate(c):
        if i<k:
            heappush(h,k)
            m+=l
        else:
            if l>r:
                while h and i>=h[0]:heappop(h)
                if h and i<h[0]:
                    m+=l
                else:
                    m+=r
            else:
                m+=r
    return m
t=int(input())
print('\n'.join(str(solve())for _ in range(t)))

Submission status: Wrong Answer

Solution code:
import heapq

def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        KLR = [tuple(map(int, input().split())) for _ in range(N)]
        KLR.sort()
        H = []
        T = []
        s = 0
        for k, l, r in KLR:
            s += r
            if l - r >= 0:
                heapq.heappush(H, (l - r, k))
                while len(H) > k:
                    T.append(heapq.heappop(H))
            else:
                T.append((l - r, k))
        s += sum(l for l, k in H)
        H = []
        T.sort(key = lambda x: -x[1])
        for l, k in T:
            heapq.heappush(H, (l, N - k))
            while len(H) > N - k:
                s += heapq.heappop(H)[0]

        print(s)
main()

Submission status: Wrong Answer

Solution code:
T = int(input())
mapping = [[-1, -1] for _ in range(2*100000)]
ans_l = [0 for _ in range(T)]
for t in range(T):
    ans = 0
    N = int(input())
    for i in range(N):
        K, L, R = map(int, input().split())
        if mapping[K-1][1] != t:
            ans += max(L, R)
            mapping[K-1][0] = max(L, R)
            mapping[K-1][1] = t
        elif mapping[K-1][0] > L or mapping[K-1][0] > R:
            ans += max(L, R)
    ans_l[t-1] = ans
for a in ans_l:
    print(a)

Submission status: Wrong Answer

Solution code:
T=int(input())
for case in range(T):
    N=int(input())
    Left=[]
    Right=[]
    Middle=[]
    for i in range(N):
        k,l,r=map(int,input().split())
        if k==N or l==r:
            Middle.append((k,l,r))
        elif l<r:
            Right.append((k,l,r))
        else:
            Left.append((k,l,r))
    Left.sort(key=lambda x:(x[0],x[1]-x[2]))
    Right.sort(key=lambda x:(-x[0],x[2]-x[1]))
    ans=0
    i=1
    for x in Left:
        k,l,r=x
        if i<=k:
            ans+=l
            i+=1
        else:
            ans+=r
    i=N
    for x in Right:
        k,l,r=x
        if i>k:
            ans+=r
            i-=1
        else:
            ans+=l
    for x in Middle:
        k,l,r=x
        ans+=l
    print(ans)

Submission status: Wrong Answer

Solution code:
T=int(input())
for t in range(T):
    N=int(input())
    KLR=sorted([list(map(int,input().split())) for i in range(N)],key=lambda x:x[1]-x[2])
    a=0
    L,R=list(range(-1,N+1)),list(range(1,N+3))
    f=0
    for k,l,r in KLR:
        if l==r or k==N:
            a+=l
        elif l>r:
            if L[R[k]]>0:
                a+=l
                L[R[k]],R[L[k]]=L[k],R[k]
            else:
                a+=r
        else:
            if f==0:
                f=1
                L,R=list(range(-1,N+1)),list(range(1,N+3))
            if R[L[k]]<=N:
                a+=r
                L[R[k]],R[L[k]]=L[k],R[k]
            else:
                a+=l
    print(a)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import*
input=sys.stdin.buffer.readline
def solve():
    n=int(input())
    c=sorted([[*map(int,input().split())]for _ in range(n)],key=lambda x:x[2]-x[1])
    m=0
    h=[]
    for i,(k,l,r)in enumerate(c):
        if i<k:
            heappush(h,k)
            m+=l
        else:
            if l>r:
                while h and i>=h[0]:heappop(h)
                if h and i<h[0]:
                    m+=l
                else:
                    m+=r
            else:
                m+=r
    return m
t=int(input())
print('\n'.join(str(solve())for _ in range(t)))

Submission status: Wrong Answer

Solution code:
import heapq

def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        KLR = [tuple(map(int, input().split())) for _ in range(N)]
        KLR.sort()
        H = []
        s = 0
        for k, l, r in KLR:
            s += r
            heapq.heappush(H, (l - r, k))
            while len(H) > k or (H and H[0][0] < 0 and H[0][1] < len(H)):
                heapq.heappop(H)
        print(s + sum(l for l, k in H))
main()

Submission status: Wrong Answer

Solution code:
def calc(cammels):
    ans = 0
    n = len(cammels)
    cammels.sort()
    cammels_pos = 0
    for i in range(n):
        (k, score) = cammels[i]
        if cammels_pos + 1 <= k:
            ans += -score
            cammels_pos += 1
    return ans

def solve():
    n = int(input())
    base = 0
    lefts=[]
    rights=[]
    for i in range(n):
        k, l, r = map(int, input().split())
        base += min(l, r)
        if l > r:
            lefts.append((k, -(l - r)))
        if r > l:
            if k != n:
                rights.append((n-k, -(r - l)))

    print(base + calc(lefts) + calc(rights))
            


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

main()

Submission status: Wrong Answer

Solution code:
T = int(input())
#S = str(input())
#L, R, d = map(int, input().split())
#A = list(map(int, input().split()))
for i in range(T):
  N = int(input())
  start = 0
  aa = [[] for i in range(N)]
  for j in range(N):
    k, l, r = map(int, input().split())
    aa[k - 1].append(r - l)
    start += l
  #print(aa, start)
  
  front, back = 0, 0  
  for i in range(N):
    nn = aa[i]
    for j in nn:
      if (j < 0):
        if (front < i + 1):
          front += 1
        else:
          start += j
  for i in range(1, N + 1):
    nn = aa[-i]
    for j in nn:
      if j > 0:
        if (i - 1) - back > 0:
          back += 1
          start += j
        
        
  
  
  print(start)

Submission status: Wrong Answer

Solution code:
import heapq

def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        KLR = [tuple(map(int, input().split())) for _ in range(N)]
        KLR.sort()
        H = []
        s = 0
        for k, l, r in KLR:
            s += r
            heapq.heappush(H, (l - r, k))
            while len(H) > k or (H and H[0][1]<= len(H)):
                heapq.heappop(H)
        print(s + sum(l for l, k in H))
main()

Submission status: Wrong Answer

Solution code:
T=int(input())

for t in range(T):
    N=int(input())
    KLR = [tuple(map(int,input().split())) for _ in range(N)]
    DKLR2 = [(R-L, K, i) for i,(K,L,R) in enumerate(KLR) if R-L>0]
    DKLR = [(L-R, K, i) for i,(K,L,R) in enumerate(KLR) if R-L<=0]
    DKLR = sorted(DKLR, reverse=True)
    DKLR2 = sorted(DKLR2, reverse=True)
    res = 0
    left = 0
    right = 0
    for dv,k,i in DKLR:
        if k!=0:
            left += 1
            res += KLR[i][1]
        else:
            res += KLR[i][2]
    for dv,k,i in DKLR2:
        if k!=N:
            right += 1
            res += KLR[i][2]
        else:
            res += KLR[i][1]
    print(res)

Submission status: Wrong Answer

Solution code:
t=int(input())
for _ in range(t):
    a=[]
    for _ in range(int(input())):
        a.append([int(x) for x in input().split()])
    fronta = [t for t in a if t[1] >= t[2]]
    backa = [t for t in a if t[1] < t[2]]
    fronta = sorted(fronta, key=lambda x: (x[0], x[1]))
    backa = sorted(backa, key=lambda x: (x[0], x[2]))
    s = 0
    i = 1
    for c in fronta+backa:
        if i <= c[0]:
            s += c[1]
        else:
            s += c[2]
        i += 1
    print(s)

Submission status: Wrong Answer

Solution code:
t = int(input())
for _ in range(t):
    n = int(input())
    a = []
    b = []
    for _ in range(n):
        k,l,r = map(int, input().split())
        if l>r:
            a.append((k,l,r))
        else:
            b.append((k,l,r))
    a.sort(key=lambda x: x[0]*1000000 - x[1])
    b.sort(key=lambda x: x[0]*1000000 + x[2])

    ans = 0
    for i,(k,l,r) in enumerate(a+b):
        if i+1<=k:
            ans += l
        else:
            ans += r
    print(ans)

Submission status: Wrong Answer

Solution code:
t = int(input())
for _ in range(t):
    n = int(input())
    a = []
    b = []
    for _ in range(n):
        k,l,r = map(int, input().split())
        if l>r:
            a.append((k,l,r))
        else:
            b.append((k,l,r))
    a.sort(key=lambda x:x[0])
    b.sort(key=lambda x: x[0])

    ans = 0
    for i,(k,l,r) in enumerate(a+b):
        if i+1<=k:
            ans += l
        else:
            ans += r
    print(ans)

Submission status: Wrong Answer

Solution code:
T=int(input())
class BIT:
    def __init__(self,N):
        self.N=N
        self.data=[0]*(N+1)
    def add(self,i,x):
        i+=1
        while i<=self.N:
            self.data[i]+=x
            i+=i&-i
    def sum(self,a,b):
        if a>0:
            r=self.sum(0,b)-self.sum(0,a)
        else:
            r=0
            i=b
            while i>0:
                r+=self.data[i]
                i-=i&-i
        return r
for t in range(T):
    N=int(input())
    KLR=sorted([list(map(int,input().split())) for i in range(N)],key=lambda x:x[1]-x[2])
    a=0
    b=BIT(N)
    f=0
    for k,l,r in KLR:
        if l==r:
            a+=l
        elif l>r:
            if b.sum(0,k)<k:
                a+=l
                b.add(k-1,1)
            else:
                a+=r
        else:
            if f==0:
                f=1
                b.data=[0]*(N+1)
            if b.sum(k,N)<k<N:
                a+=r
                b.add(k-1,1)
            else:
                a+=l
    print(a)

Submission status: Wrong Answer

Solution code:
T = int(input())
#S = str(input())
#L, R, d = map(int, input().split())
#A = list(map(int, input().split()))
for i in range(T):
  N = int(input())
  start = 0
  aa = [[] for i in range(N)]
  for j in range(N):
    k, l, r = map(int, input().split())
    aa[k - 1].append(r - l)
    start += l
  #print(aa, start)
  
  front, back = 0, 0  
  for i in range(N):
    nn = aa[i]
    for j in nn:
      if (j < 0):
        if (front < i + 1):
          front += 1
        else:
          start += j
      elif j > 0:
        if back < (N - i - 1):
          start += j
          back += 1
  print(start)

Submission status: Time Limit Exceeded

Solution code:
T = int(input())
for fakevar in range(T):
	N=int(input())
	p=[]
	n=[]
	min_p=0
	min_n=0
	for fakevar2 in range(N):
		K,L,R=map(int, input().split())
		if L-R>=0:
			p+=[[L-R,K-1]]
			min_p+=R
		else:
			n+=[[R-L,N-K-1]]
			min_n+=L
	
	p.sort(key=lambda x: x[0], reverse=True)
	n.sort(key=lambda x: x[0], reverse=True)
	p_set=set([])
	n_set=set([])
	p_score=0
	n_score=0
	for i in range(len(p)):
		j=min(p[i][1],len(p)-1)
		while j in p_set and j>=0:
			j+=(-1)
		
		if j>=0:
			p_set.add(j)
			p_score+=p[i][0]
	
	for i in range(len(n)):
		j=min(n[i][1],len(n)-1)
		while j in n_set and j>=0:
			j+=(-1)
		
		if j>=0:
			n_set.add(j)
			n_score+=n[i][0]
	
	print(p_score+n_score+min_p+min_n)

		





# 2darray [[0] * 4 for i in range(3)]

Submission status: Time Limit Exceeded

Solution code:
T = int(input())
for fakevar in range(T):
	N=int(input())
	p=[]
	n=[]
	min_p=0
	min_n=0
	for fakevar2 in range(N):
		K,L,R=map(int, input().split())
		if L-R>=0:
			p+=[[L-R,K-1]]
			min_p+=R
		else:
			n+=[[R-L,N-K-1]]
			min_n+=L
	
	p.sort(key=lambda x: x[0], reverse=True)
	n.sort(key=lambda x: x[0], reverse=True)
	p_array=[-1]*len(p)
	n_array=[-1]*len(n)
	p_score=0
	n_score=0
	for i in range(len(p)):
		j=min(p[i][1],len(p)-1)
		while p_array[j]>-1 and j>=0:
			j+=(-1)
		
		if j>=0:
			p_array[j]=p[i][0]
			p_score+=p[i][0]
	
	for i in range(len(n)):
		j=min(n[i][1],len(n)-1)
		while n_array[j]>-1 and j>=0:
			j+=(-1)
		
		if j>=0:
			n_array[j]=n[i][0]
			n_score+=n[i][0]
	
	print(p_score+n_score+min_p+min_n)

		





# 2darray [[0] * 4 for i in range(3)]