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: Time Limit Exceeded

Solution code:
from collections import namedtuple
from pprint import pp

Camel = namedtuple("Camel", "k l r crt preference avail".split(" "))

def read_int():
    return int(input())

def read_int_array():
    return [int(ss) for ss in input().split()]

def solution():
    n = read_int()
    camels = []

    for _ in range(n):
        k, l, r = read_int_array()
        preference = None
        if l > r:
            preference = "l"
        elif l < r:
            preference = "r"
        camels.append(Camel(k - 1, l, r, None, preference, None))

    camels = sorted(camels, key = lambda c: -abs(c.l - c.r))

    arrangement = [None for _ in camels]

    lefties = [None for _ in camels]
    righties = [None for _ in camels]

    lcount = 0
    rcount = 0

    total_happy = 0

    for c in camels:
        if c.preference is None:
            total_happy += c.r

        elif c.preference == "l":
            total_happy += c.r
            for i in range(c.k, -1, -1):
                if lefties[i] is None:
                    lefties[i] = c
                    lcount += 1
                    total_happy += c.l - c.r
                    break

        else: # "r"
            total_happy += c.l
            for i in range(c.k + 1, n):
                if righties[i] is None:
                    righties[i] = c
                    rcount += 1
                    total_happy += c.r - c.l
                    break

    return total_happy

def main():
    t = read_int()

    for i in range(t):
        s = solution()
        print(s)


main()

Submission status: Time Limit Exceeded

Solution code:
T = int(input())


def solve(camels):
    plus = 0
    camels.sort(reverse=True)
    S = []
    for i in range(len(camels), 0, -1):
        if i == len(camels):
            for camel in camels:
                k = camel[0]
                lr = camel[1]
                if k > i:
                    S.append(lr)
        for camel in camels:
            k = camel[0]
            lr = camel[1]
            if k == i:
                S.append(lr)
            if k < i:
                break

        if S:
            S.sort(reverse=True)
            plus += S.pop(0)
    return plus

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

    score = 0
    l_camel = []
    r_camel = []
    for _ in range(N):
        k, l, r = map(int, input().split())
        if l > r:
            l_camel.append([k, l-r])
            score += r
        elif l < r:
            r_camel.append([N-k, r-l])
            score += l
        else:
            score += r
    score += solve(l_camel)
    score += solve(r_camel)
    print(score)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import heapq

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

    c = [tuple(map(int, input().split())) for _ in range(n)]

    # 前にいる方が嬉しい
    pc = [cc for cc in c if cc[1] >= cc[2]]
    pcl = len(pc)
    pc.sort(key=lambda x: x[0], reverse=True)
    ps = sum([cc[2] for cc in pc])
    pcc = []
    pg = 0
    for i in range(pcl):
        k = pcl-i
        # 条件に当てはまるラクダ
        ci = 0
        for cc in pc:
            if cc[0] < k:
                break
            ci += 1
            heapq.heappush(pcc, cc[2]-cc[1])
        pc = pc[ci:]
        if pcc:
            pg += -heapq.heappop(pcc)
    # 後ろにいる方が嬉しい
    nc = [cc for cc in c if cc[1] < cc[2]]
    ncl = len(nc)
    nc.sort(key=lambda x: x[0])
    ns = sum([cc[1] for cc in nc])
    ncc = []
    ng = 0
    for i in range(ncl):
        k = n-ncl+i+1
        # 条件に当てはまるラクダ
        ci = 0
        for cc in nc:
            if cc[0] >= k:
                break
            ci += 1
            heapq.heappush(ncc, cc[1]-cc[2])
        nc = nc[ci:]
        if ncc:
            ng += -heapq.heappop(ncc)
    print(ps+pg+ns+ng)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

    c = [tuple(map(int, input().split())) for _ in range(n)]

    # 前にいる方が嬉しい
    pc = [cc for cc in c if cc[1] >= cc[2]]
    pcl = len(pc)
    pc.sort(key=lambda x: x[0], reverse=True)
    ps = sum([cc[2] for cc in pc])
    pcc = []
    pg = 0
    for i in range(pcl):
        k = pcl-i
        # 条件に当てはまるラクダ
        ci = 0
        for cc in pc:
            if cc[0] < k:
                break
            ci += 1
            bisect.insort(pcc, cc[1]-cc[2])
        pc = pc[ci:]
        if len(pcc) > 0:
            pg += pcc[-1]
            pcc = pcc[:-1]
    # 後ろにいる方が嬉しい
    nc = [cc for cc in c if cc[1] < cc[2]]
    ncl = len(nc)
    nc.sort(key=lambda x: x[0])
    ns = sum([cc[1] for cc in nc])
    ncc = []
    ng = 0
    for i in range(ncl):
        k = n-ncl+i+1
        # 条件に当てはまるラクダ
        ci = 0
        for cc in nc:
            if cc[0] >= k:
                break
            ci += 1
            bisect.insort(ncc, cc[2]-cc[1])
        nc = nc[ci:]
        if len(ncc) > 0:
            ng += ncc[-1]
            ncc = ncc[:-1]
    print(ps+pg+ns+ng)

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
T = int(input())
for vasakwklmkda in range(T):
	N=int(input())
	p=[]
	n=[]
	min_p=0
	min_n=0
	for nvkasvdlkasdfnnnaejkf 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)]

Submission status: Time Limit Exceeded

Solution code:
#!python3

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

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

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

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

        ls = len(a1)
        vis = [None]*N
        for diff, i in a1:
            j = min(i, ls) - 1
            v2 = [[-1]]
            while j >= 0:
                v1 = vis[j]
                if v1 == None:
                    val += diff
                    v2[0][0] = j-1
                    vis[j] = v2
                    break
                j, v1[0] = v1[0][0], v2[0]


        for diff, i in a2:
            j, v2 = max(i, ls), [[-1]]
            while j < N:
                v1 = vis[j]
                if not v1:
                    val += diff
                    v2[0][0] = j + 1
                    vis[j] = v2
                    break
                j, v1[0] = v1[0][0], v2[0]

        ans.append(val)

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



if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
#!python3

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

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

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

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

        ls = len(a1)
        vis = [0]*N
        for diff, i in a1:
            for j in reversed(range(min(i,ls))):
                if vis[j]: continue
                vis[j] = 1
                val += diff
                break

        for diff, i in a2:
            for j in range(max(i, ls), N):
                if vis[j]: continue
                vis[j] = 1
                val += diff
                break

        ans.append(val)

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



if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop,heapify

pl = []
pr = []

def f(p):
  res = 0
  s = len(p)
  for i in range(s):
    if p[i][0] > s:
      p[i][0] = -s
    else:
      p[i][0] *= -1
  heapify(p)
  hq = []
  for i in range(s,0,-1):
    #print('p:',p,'i:',i)
    while(len(p) > 0 and p[0][0] == -i):
      a,b = heappop(p)
      heappush(hq,-b)
    #print('hq:',hq)
    if len(hq) > 0:
      b = heappop(hq)
      #print('b:',b)
      res -= b
  return res

def solve():
  ans = 0
  n = int(input())
  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: Time Limit Exceeded

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)
    for i in range(N,0,-1):
      if len(left[i]):
        ans[t] += left[i][-1]
        for l in left[i][:-1]:
          insort_right(left[i-1],l)
    for i in range(2,N+1):
      if len(right[i]):
        ans[t] += right[i][-1]
        for l in right[i][:-1]:
          insort_right(right[i+1],l)
  return ans
print(*solve(),sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:k,l,r=t=[*map(int,i().split())];x+=[t]*(l>r);y+=[[n-k,r,l]]*(l<=r)
 for x in x,y:
  x.sort();n,*h=len(x),
  while h+x:
   while[[n]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[2-(n>0)]
   n-=1
 print(s)

Submission status: Time Limit Exceeded

Solution code:


# point update
# range query
class SegmentTreeNode:
	def __init__(self, start, end, initial, merge):
#		print("s", start, end)
		self.start = start
		self.end = end
		self.width = end - start
		self.merge = merge
		self.initial = initial
		if self.width > 1:
			w2 = self.width // 2
			self.left = SegmentTreeNode(start, start + w2, initial, merge)
			self.right = SegmentTreeNode(start + w2, end, initial, merge)
			self.value = self.merge(self.left.value, self.right.value)
		else:
			self.value = self.initial

	def update(self, index, value):
		if self.start <= index and index < self.end:
			if self.width == 1:
				self.value = value
			else:
				self.left.update(index, value)
				self.right.update(index, value)
				self.value = self.merge(self.left.value, self.right.value)
	
	def pick(self, start, end):
		if start <= self.start and self.end <= end:
			return self.value
		elif self.start < end and self.end > start:
#			m = self.merge(self.left.pick(start, end), self.right.pick(start, end))
#			print(start, end, m)
			return self.merge(self.left.pick(start, end), self.right.pick(start, end))
		else:
			return self.initial
	
	def to_list(self, items):
		if self.width == 1:
			items.append(self.value)
		else:
			self.left.to_list(items)
			self.right.to_list(items)
	
class SegmentTree:
	def __init__(self, n, *, merge, initial = None):
		width = 1
		while width < n:
			width *= 2
		self.root = SegmentTreeNode(0, width, initial, merge)
		self.root.value = 0
		self.capacity = width
	
	def update(self, index, value):
		self.root.update(index, value)
	
	def pick(self, start, end):
		return self.root.pick(start, end)
	
	def to_list(self):
		items = []
		self.root.to_list(items)
		return items
	

def merge(l, r):
	if r[1]:
		return r
	else:
		return l

import sys

T = int(input())

def calc(camels):
	camels.sort()
	count = len(camels)
	st = SegmentTree(count, merge = merge, initial = (None, False))
	for i in range(count):
		st.update(i, (i, True))
	for i in range(count + 1, st.capacity):
		st.update(i, (i, False))
	score = 0
	train = [None] * N
	for D, L, R, K in camels:
		if K >= 0:
			i, c = st.pick(0, min(K, count))
#			print(st.to_list(), file = sys.stderr)
#			print(L, R, K, i, c, file = sys.stderr)
			if c:
#				print("x", i, L, R, file = sys.stderr)
				st.update(i, (i, False))
				train[i] = (L, R)
				score += L
			else:
				score += R
		else:
			score += R
#	print(train, file = sys.stderr)
	return score

for t in range(T):
#	print(f"t = {t}", file = sys.stderr)
	N = int(input())
	
	camels_l = []
	camels_r = []
	
	count_r = 0
	for _ in range(N):
		K, L, R = map(int, input().split())
		D = L - R
		if D >= 0:
			camels_l.append((-D, L, R, K))
		else:
			camels_r.append((D, R, L, N - K))
	
#	print(camels_l)
#	print(camels_r)
	
	print(calc(camels_l) + calc(camels_r))

Submission status: Time Limit Exceeded

Solution code:
from heapq import*
i=input
for _ in'_'*int(i()):
 n,s,x,*y=int(i()),0,[];exec('k,l,r=t=[*map(int,i().split())];x+=[t]*(l>r);y+=[(n-k,r,l)]*(l<=r);'*n)
 for x in x,y:
  x.sort();n,*h=len(x),
  while n:
   n-=1
   while x and x[-1][0]>n:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[1]
  for*_,r in x+h:s+=r
 print(s)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import deque
  import sys
  input = sys.stdin.readline
  T = int(input())
  def res_1(lis,ans):
    flag = [False] * (N)
    for klr in lis:
      x = klr[0]
      for _ in range(N):
        if x<0:
          ans += klr[2]
          break
        if flag[x]:
          x -= 1
        else:
          flag[x] = True
          ans += klr[1]
          break
    return ans
  
  def res_2(lis,ans):
    flag = [False] * (N)
    for klr in right:
      x = klr[0] + 1
      for _ in range(N):
        if x>=N:
          ans += klr[1]
          break
        if flag[x]:
          x += 1
        else:
          flag[x] = True
          ans += klr[2]
          break
          
    return ans
  for _ in range(T):
    N = int(input())
    KLR = [list(map(int,input().split())) for _ in range(N)]
    left = deque([])
    right = deque([])
    ans = 0
    for K,L,R in KLR:
      x = L - R
      if x==0:
        ans += L
      elif x>0:
        left.append([K-1,L,R,x])
      else:
        right.append([K-1,L,R,x])

    left = sorted(left,key = lambda x:x[3],reverse = True)
    right = sorted(right, key = lambda x:x[3])
    ans = res_1(left,ans)
    ans = res_2(right,ans)

    print(ans)
    
main()

Submission status: Time Limit Exceeded

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

T = int(input())

def solve():
    N = int(input())
    KLR = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[2]-x[1])
    line = [-1]*N
    ans = 0
    for k, l, r in KLR:
        if l < r:
            break
        flg = False
        for i in range(k-1, -1, -1):
            if line[i] == -1:
                line[i] = 1
                flg = True
                break
        if flg:
            ans += l
        else:
            ans += r
    line = [-1] * N
    for k, l, r in KLR[::-1]:
        if l >= r:
            break
        flg = False
        for i in range(k, N):
            if line[i] == -1:
                line[i] = 1
                flg = True
                break
        if flg:
            ans += r
        else:
            ans += l
    print(ans)


for _ in range(T):
    solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    camels = [tuple(map(int, input().split())) for _ in range(N)]

    camels.sort(key=lambda x: abs(x[1] - x[2]), reverse=True)

    L, R = [False] * N, [False] * N
    full_idx_l, full_idx_r = 0, N - 1
    ans = 0
    for k, l, r in camels:
        if l > r:
            k -= 1
            if k < full_idx_l:
                ans += r
                continue
            while L[k]:
                k -= 1
                if k < full_idx_l:
                    ans += r
                    continue
            L[k] = True
            ans += l
            while full_idx_l < N and L[full_idx_l]:
                full_idx_l += 1
        else:
            if k > full_idx_r:
                ans += l
                continue
            while R[k]:
                k += 1
                if k > full_idx_r:
                    ans += l
                    continue
            R[k] = True
            ans += r
            while full_idx_r >= 0 and R[full_idx_r]:
                full_idx_r -= 1
    print(ans)


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

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import deque
  import sys
  input = sys.stdin.readline
  T = int(input())
  for _ in range(T):
    N = int(input())
    KLR = [list(map(int,input().split())) for _ in range(N)]
    left = deque([])
    right = deque([])
    ans = 0
    for K,L,R in KLR:
      x = L - R
      if x==0:
        ans += L
      elif x>0:
        left.append([K-1,L,R,x])
      else:
        right.append([K-1,L,R,x])

    left = sorted(left,key = lambda x:x[3],reverse = True)
    right = sorted(right, key = lambda x:x[3])
    flag = [False] * (N)
    for klr in left:
      x = klr[0]
      for _ in range(N):
        if x<0:
          ans += klr[2]
          break
        if flag[x]:
          x -= 1
        else:
          flag[x] = True
          ans += klr[1]
          break
    flag = [False] * (N)
    for klr in right:
      x = klr[0] + 1
      for _ in range(N):
        if x>=N:
          ans += klr[1]
          break
        if flag[x]:
          x += 1
        else:
          flag[x] = True
          ans += klr[2]
          break

    print(ans)
    
main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class SegtreeMax():
    def __init__(self, n):
        self.inf = 10 ** 16
        tree_width = 2
        while tree_width < n:
            tree_width *= 2
        self.tree_width = tree_width
        self.tree = [0] * (tree_width * 2 - 1)

    def update(self, i, a):
        seg_i = self.tree_width - 1 + i
        self.tree[seg_i] = a
        while seg_i != 0:
            seg_i = (seg_i - 1) // 2
            self.tree[seg_i] = max(self.tree[seg_i * 2 + 1], self.tree[seg_i * 2 + 2])

    def element(self, i):
        return self.tree[self.tree_width - 1 + i]

    # [l,r)の最小値
    def max(self, l, r, seg_i=0, segL=0, segR=-1):
        if segR == -1: segR = self.tree_width
        if r <= segL or segR <= l: return 0
        if l <= segL and segR <= r: return self.tree[seg_i]
        segM = (segL + segR) // 2
        ret0 = self.max(l, r, seg_i * 2 + 1, segL, segM)
        ret1 = self.max(l, r, seg_i * 2 + 2, segM, segR)
        return max(ret0, ret1)

for _ in range(II()):
    n=II()
    hp=[]
    hpr=[]
    ans=0
    for _ in range(n):
        k,l,r=MI()
        if r<l:heappush(hp,(r-l,l,r,k))
        elif r>l:heappush(hpr,(-r+l,l,r,k))
        else:ans+=r

    st=SegtreeMax(n+5)
    for i in range(n+1):st.update(i,i)
    while hp:
        d,l,r,k=heappop(hp)
        i=st.max(0,k+1)
        if i:
            ans+=l
            st.update(i,0)
        else:
            ans+=r

    st=SegtreeMax(n+5)
    for i in range(n+1):st.update(i,i)
    while hpr:
        d,l,r,k=heappop(hpr)
        k=n-k
        i=st.max(0,k+1)
        if i:
            ans+=r
            st.update(i,0)
        else:
            ans+=l

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import deque
  import sys
  input = sys.stdin.readline
  T = int(input())
  for _ in range(T):
    N = int(input())
    KLR = [list(map(int,input().split())) for _ in range(N)]
    left = deque([])
    right = deque([])
    mid = deque([])
    for K,L,R in KLR:
      x = L - R
      if x==0:
        mid.append([K-1,L,R,x])
      elif x>0:
        left.append([K-1,L,R,x])
      else:
        right.append([K-1,L,R,x])

    left = sorted(left,key = lambda x:x[3],reverse = True)
    right = sorted(right, key = lambda x:x[3])
    flag = [False] * (N)
    ans = 0
    for klr in left:
      x = klr[0]
      for _ in range(N):
        if x<0:
          ans += klr[2]
          break
        if flag[x]:
          x -= 1
        else:
          flag[x] = True
          ans += klr[1]
          break
    flag = [False] * (N)
    for klr in right:
      x = klr[0] + 1
      for _ in range(N):
        if x>=N:
          ans += klr[1]
          break
        if flag[x]:
          x += 1
        else:
          flag[x] = True
          ans += klr[2]
          break
    for klr in mid:
      ans += klr[1]

    print(ans)
    
main()

Submission status: Time Limit Exceeded

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-1,l,r))
   left = sorted(left, key=lambda x: x[2]-x[1])
   right = sorted(right, key=lambda x: x[1]-x[2])
   ans = 0
   dl = {}
   dr = {}
   for i,(k,l,r) in enumerate(left):
      while k in dl and k >= 0:
         k -= 1
      if k == -1:
         ans += r
      else:
         dl[k] = i
         ans += l
   for i,(k,l,r) in enumerate(right):
      while k in dr and k >= 0:
         k -= 1
      if k == -1:
         ans += l
      else:
         dr[k] = i
         ans += r
   # 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: Time Limit Exceeded

Solution code:
def main():
  from collections import deque
  import sys
  input = sys.stdin.readline
  T = int(input())
  for _ in range(T):
    N = int(input())
    KLR = [list(map(int,input().split())) for _ in range(N)]
    left = deque([])
    right = deque([])
    mid = deque([])
    for K,L,R in KLR:
      x = L - R
      if x==0:
        mid.append([K-1,L,R,x])
      elif x>0:
        left.append([K-1,L,R,x])
      else:
        right.append([K-1,L,R,x])

    left = sorted(left,key = lambda x:x[3],reverse = True)
    right = sorted(right, key = lambda x:x[3])
    flag = [False] * (N)
    ans = 0
    for i in range(len(left)):
      klr = left[i]
      x = klr[0]
      while True:
        if x<0:
          ans += klr[2]
          break
        if flag[x]:
          x -= 1
        else:
          flag[x] = True
          ans += klr[1]
          break
    flag = [False] * (N)
    for i in range(len(right)):
      klr = right[i]
      x = klr[0] + 1
      while True:
        if x>=N:
          ans += klr[1]
          break
        if flag[x]:
          x += 1
        else:
          flag[x] = True
          ans += klr[2]
          break
    for i in range(len(mid)):
      ans += mid[i][1]

    print(ans)
    
main()

Submission status: Time Limit Exceeded

Solution code:
T = int(input())
from collections import deque
for _ in range(T):
  N = int(input())
  KLR = [list(map(int,input().split())) for _ in range(N)]
  left = deque([])
  right = deque([])
  mid = deque([])
  for K,L,R in KLR:
    x = L - R
    if x==0:
      mid.append([K-1,L,R,x])
    elif x>0:
      left.append([K-1,L,R,x])
    else:
      right.append([K-1,L,R,x])

  left = sorted(left,key = lambda x:x[3],reverse = True)
  right = sorted(right, key = lambda x:x[3])
  flag = [False] * (N)
  ans = 0
  for i in range(len(left)):
    klr = left[i]
    x = klr[0]
    while True:
      if x<0:
        ans += klr[2]
        break
      if flag[x]:
        x -= 1
      else:
        flag[x] = True
        ans += klr[1]
        break
  flag = [False] * (N)
  for i in range(len(right)):
    klr = right[i]
    x = klr[0] + 1
    while True:
      if x>=N:
        ans += klr[1]
        break
      if flag[x]:
        x += 1
      else:
        flag[x] = True
        ans += klr[2]
        break
  for i in range(len(mid)):
    ans += mid[i][1]
    
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx
import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    G = nx.MultiDiGraph()
    # s: source t: sink
    # 0 ... N-1: camel
    # N ... 2*N-1: loc1
    # 2*N ... 3*N-1: loc2
    G.add_node('s', demand=-N)
    G.add_node('t', demand=N)
    for i in range(N):
        G.add_edge('s', i, weight=0, capacity=1)
    for i in range(N-1):
        G.add_edge(N+i, N+i+1, weight=0, capacity=i+1)
    for i in range(N-1):
        G.add_edge(2*N+i+1, 2*N+i, weight=0, capacity=N-i-1)
    G.add_edge(2*N-1, 't', weight=0, capacity=N)
    G.add_edge(2*N, 't', weight=0, capacity=N)
    for i in range(N):
        K, L, R = map(int, input().split())
        K -= 1
        G.add_edge(i, N+K, weight=-L, capacity=1)
        if K < N - 1:
            G.add_edge(i, 2*N+K+1, weight=-R, capacity=1)
    print(-nx.min_cost_flow_cost(G))

Submission status: Accepted

Solution code:
import heapq as hp
# heapq.heappush(heap,item)
# heapq.heppop(heap) 最小値　最初のやつの取り出し
t=int(input())
for i in range(t):
    n=int(input())
# 左からkまでなら、+x lef[k]=[3,4,5]
    lef=[[] for i in range(n+1)]
    rig=[[] for i in range(n+1)]
    a=[]
    hp.heapify(a)
    ans=0
    lefcnt=0

    for i in range(n):
        k,l,r=map(int,input().split())
        if(l>=r):
            ans+=r
            lefcnt+=1
            tmp=l-r
            lef[k].append(tmp)
        else:
            ans+=l
            tmp=r-l
            rig[n-k].append(tmp)
    for i in range(n,lefcnt,-1):
        for j in lef[i]:
            hp.heappush(a,-j)           
    for i in range(lefcnt,0,-1):
        for j in lef[i]:
            hp.heappush(a,-j)
        if(a):
            tmp=hp.heappop(a)*(-1)
            ans+=tmp

    a=[]
    hp.heapify(a)
    for i in range(n,n-lefcnt,-1):
        for j in rig[i]:
            hp.heappush(a,-j)    
    for i in range(n-lefcnt,0,-1):
        for j in rig[i]:
            hp.heappush(a,-j)
        if(a):
            tmp=hp.heappop(a)*(-1)
            ans+=tmp
    print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict


def solve(N, klrs):
    # ベースの嬉しさは sum_i min(Li, Ri)
    # (1) Li > Ri なるラクダ
    #   なるべく先頭側に寄せることで追加の嬉しさを獲得できる
    # (2) Li < Ri なるラクダ
    #   なるべく末尾側に寄せることで追加の嬉しさを獲得できる
    # => (1), (2) それぞれで追加できる嬉しさの最大値を求めてベースに足す
    left_camels, right_camels = defaultdict(list), defaultdict(list)
    for i, (k, l, r) in enumerate(klrs):
        if l > r:
            left_camels[k].append(i)
        elif l < r:
            right_camels[k + 1].append(i)
    # (1)
    que = []
    for k in range(N):
        for i in left_camels[k]:
            _, l, r = klrs[i]
            heapq.heappush(que, l - r)
        while len(que) > k + 1:
            heapq.heappop(que)
    p_1 = 0
    while len(que) > 0:
        p_1 += heapq.heappop(que)    
    # (2)
    que = []
    for k in range(N - 1, -1, -1):
        for i in right_camels[k]:
            _, l, r = klrs[i]
            heapq.heappush(que, r - l)
        while len(que) > N - k:
            heapq.heappop(que)
    p_2 = 0
    while len(que) > 0:
        p_2 += heapq.heappop(que)
    return p_1 + p_2 + sum(min(l, r) for _, l, r in klrs)


def main():
    T = int(input())
    ans = [0] * T
    for t in range(T):
        N = int(input())
        klrs = list()
        for _ in range(N):
            k, l, r = map(int, input().split())
            klrs.append([k - 1, l, r])
        ans[t] = solve(N, klrs)
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()