Problem:


Score : 800 points

Problem Statement

Takahashi and Aoki will take N exams numbered 1 to N.
They have decided to compete in these exams.
The winner will be determined as follows:

For each exam i, Takahashi decides its importance c_i, which must be an integer between l_i and u_i (inclusive).

Let A be \sum_{i=1}^{N} c_i \times (Takahashi's score on Exam i), and B be \sum_{i=1}^{N} c_i \times (Aoki's score on Exam i). Takahashi wins if A \geq B, and Aoki wins if A < B.

Takahashi knows that Aoki will score b_i on Exam i, with his supernatural power.

Takahashi himself, on the other hand, will score 0 on all the exams without studying more. For each hour of study, he can increase his score on some exam by 1. (He can only study for an integer number of hours.)
However, he cannot score more than X on an exam, since the perfect score for all the exams is X.

Print the minimum number of study hours required for Takahashi to win.

Constraints

1 \leq N \leq 10^5

1 \leq X \leq 10^5

0 \leq b_i \leq X (1 \leq i \leq N)

1 \leq l_i \leq u_i \leq 10^5 (1 \leq i \leq N)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X
b_1 l_1 u_1
b_2 l_2 u_2
:
b_N l_N u_N

Output

Print the minimum number of study hours required for Takahashi to win.

Sample Input 1

2 100
85 2 3
60 1 1

Sample Output 1

115

One optimal strategy is as follows:

Choose c_1 = 3, c_2 = 1.

Study to score 100 on Exam 1 and 15 on Exam 2.

Then, A = 3 \times 100 + 1 \times 15 = 315, B = 3 \times 85 + 1 \times 60 = 315 and Takahashi will win.

Sample Input 2

2 100
85 2 3
60 10 10

Sample Output 2

77

Sample Input 3

1 100000
31415 2718 2818

Sample Output 3

31415

Sample Input 4

10 1000
451 4593 6263
324 310 6991
378 1431 7068
71 1757 9218
204 3676 4328
840 6221 9080
684 1545 8511
709 5467 8674
862 6504 9835
283 4965 9980

Sample Output 4

2540



Sample input:
2 100
85 2 3
60 1 1


Sample output:
115

Submission status: Wrong Answer

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

N, X = map(int, input().split())

q_array = []
s_array = []

score_needed = 0

for i in range(N):
    b, l, u = map(int, readline().split())
    q_array.append([b, l, u, b * l + (X - b) * u])
    s_array.append(b * l + (X - b) * u)
    score_needed += b * l

q_array = sorted(q_array, key=lambda x: -x[3])
s_array = sorted(s_array, key=lambda x: -x)

ans_min = 0
ans_max = N * X
while ans_max - ans_min > 1:
    ans = (ans_min + ans_max) // 2
    use_all = ans // X
    use_part = ans % X
    # print(use_all, use_part)
    score_get_max = 0
    score_tmp = 0
    if use_part == 0:
        score_get_max = sum(s_array[:use_all])
    else:
        score_get_max = 0
        score_tmp = 0
        for q in q_array:
            b, l, u, s = q
            score_tmp = 0
            if use_part <= b:
                score_tmp = use_part * l
            else:
                score_tmp = (b * l + (use_part - b) * u)
            if use_all > 0:
                if s_array[use_all - 1] <= s:
                    score_tmp += (sum(s_array[:use_all + 1]) - s)
                else:
                    score_tmp += sum(s_array[:use_all])
            score_get_max = max(score_get_max, score_tmp)
    # print(ans, score_get_max)
    if score_get_max >= score_needed:
        ans_max = ans
    else:
        ans_min = ans

print(ans_max)

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
Sum=0
M_list=[]
b_list=[]
l_list=[]
u_list=[]
Check=[True]*n
for i in range(n):
    b,l,u=map(int,input().split())
    Sum=Sum-b*l
    M_list.append([(x-b)*u+b*l,i])
    b_list.append(b)
    l_list.append(l)
    u_list.append(u)
M_list.sort(reverse=True)
i=0
while Sum<0:
    Sum=Sum+M_list[i][0]
    Check[M_list[i][1]]=False
    i=i+1
i=i-1
ans=x*i
Check[M_list[i][1]]=True
Sum=Sum-M_list[i][0]
rest=x
for j in range(n):
    s=-Sum
    if Check[j]:
        b=b_list[j]
        l=l_list[j]
        u=u_list[j]
        if s//l<=b:
            k=(s+l-1)//l
        else:
            k=b
            s=s-l*b
            k=k+(s+u-1)//u
        rest=min(rest,k)
print(ans+rest)

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
Sum=0
M_list=[]
b_list=[]
l_list=[]
u_list=[]
Check=[True]*n
for i in range(n):
    b,l,u=map(int,input().split())
    Sum=Sum-b*l
    M_list.append([(x-b)*u+b*l,i])
    b_list.append(b)
    l_list.append(l)
    u_list.append(u)
M_list.sort(reverse=True)
i=0
while Sum<0:
    Sum=Sum+M_list[i][0]
    Check[M_list[i][1]]=False
    i=i+1
i=i-1
ans=x*i
Check[M_list[i][1]]=True
Sum=Sum-M_list[i][0]
rest=x
for j in range(n):
    s=-Sum
    if Check[j]:
        b=b_list[j]
        l=l_list[j]
        u=u_list[j]
        if s//l<b:
            k=(s+l-1)//l
        else:
            k=b
            s=s-l*b
            k=k+(s+u-1)//u
        rest=min(rest,k)
print(ans+rest)

Submission status: Wrong Answer

Solution code:
N,X=map(int,input().split())
above=[0]*N
now=0
data=[0]*N
for i in range(N):
    b,l,u=map(int,input().split())
    above[i]=(i,b*l+(X-b)*u)
    data[i]=(b,l,u)
    now-=l*b
above.sort(key=lambda x:x[1],reverse=True)
used=set()
ans=0
for i in range(N):
    if now+above[i][1]<0:
        now+=above[i][1]
        used|={above[i][0]}
        ans+=X
    else:
        break
M=float('inf')
now*=-1
for i in range(N):
    if i in used:
        continue
    b,l,u=data[i]
    if now<=b*l:
        M=min(M,(now+l-1)//l)
    elif now<=b*l+(X-b)*u:
        M=min(M,b+(now-b*l+u-1)//u)
print(ans+M)

Submission status: Wrong Answer

Solution code:
def getlist():
	return map(int, input().split())

T = 0
N, X = getlist()
L = []

for i in range(N):
	b, l, u = getlist()
	L.append([(X - b) * u, l, u, b])
	T += b * l

L = sorted(L)


ans = 0
for i in range(len(L)):
	l = L[-1 - i][1]
	u = L[-1 - i][2]
	b = L[-1 - i][3]
	if T >= X * u - b * (u - l):
		ans += X
		T -= X * u - b * (u - l)
	else:
		val = float("inf")
		for j in range(N - i):
			ll = L[j][1]
			uu = L[j][2]
			bb = L[j][3]
			if T % ll == 0:
				ans1 = int(T // ll)
			else:
				ans1 = int(T // ll) + 1

			if (T + bb * (uu - ll)) % uu == 0:
				ans2 = int((T + bb * (uu - ll)) // uu)
			else:
				ans2 = int((T + bb * (uu - ll)) // uu) + 1

			if ans1 < val:
				val = ans1
			if ans2 < val:
				val = ans2

		ans += min(val, ans2)
		break

print(ans)

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
Sum=0
M_list=[]
b_list=[]
l_list=[]
u_list=[]
Check=[True]*n
for i in range(n):
    b,l,u=map(int,input().split())
    Sum=Sum-b*l
    M_list.append([(x-b)*u+b*l,i])
    b_list.append(b)
    l_list.append(l)
    u_list.append(u)
M_list.sort(reverse=True)
i=0
while Sum<0:
    Sum=Sum+M_list[i][0]
    Check[M_list[i][1]]=False
    i=i+1
i=i-1
ans=x*i
Check[M_list[i][1]]=True
Sum=Sum-M_list[i][0]
rest=x
for j in range(n):
    s=Sum
    if Check[j]:
        b=b_list[j]
        l=l_list[j]
        u=u_list[j]
        k=0
        while s<0:
            if k<b:
                s=s+l
            else:
                s=s+u
            k=k+1
        rest=min(rest,k)
print(ans+rest)

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
Sum=0
M_list=[]
b_list=[]
l_list=[]
u_list=[]
for i in range(n):
    b,l,u=map(int,input().split())
    Sum=Sum-b*l
    M_list.append([(x-b)*u+b*l,i])
    b_list.append(b)
    l_list.append(l)
    u_list.append(u)
M_list.sort(reverse=True)
i=0
while Sum<0:
    Sum=Sum+M_list[i][0]
    i=i+1
i=i-1
ans=x*i
Sum=Sum-M_list[i][0]
j=M_list[i][1]
b=b_list[j]
l=l_list[j]
u=u_list[j]
k=0
while Sum<0:
    if k<b:
        Sum=Sum+l
    else:
        Sum=Sum+u
    k=k+1
    ans=ans+1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,x = na()
allp = 0
d = []
data = []
ans = 0

for i in range(n):
   b,l,u = na()
   allp += l*b
   data.append([b,l,u])
   d.append([u*(x-b)+l*b,i])

d = sorted(d)
p = 0
ans = 0

while allp > 0:
   h = d.pop()
   if p+h[0] >= allp:
      t = [h[1]]
      while d:
         r = d.pop()
         if p+r[0] >= allp:
            t.append(r[1])
         else:
            break
      q = allp-p
      k = 1000000000
      for i in t:
         b = data[i][0]
         l = data[i][1]
         u = data[i][2]
         if q > b*l:
            k = min(k,b+(q-b*l-0.1)//u+1)
         else:
            k = min(k,(q-0.1)//l+1)
      ans += k
      break
   else:
      p += h[0]
      ans += x

print(int(ans))

Submission status: Wrong Answer

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,x = inm()
blu = []
pt = 0
for i in range(n):
    b,l,u = inm()
    v = u - (u-l)*b/x
    blu.append((v,b,l,u))
    pt -= l*b
blu.sort(reverse=True)

sum = 0
for z in blu:
    v,b,l,u = z
    nxtpt = pt + l*b + u*(x-b)
    ddprint("v {} b {} l {} u {} pt {} nx {}".format(v,b,l,u,pt,nxtpt))
    if nxtpt < 0:
        pt = nxtpt
        sum += x
        continue
    elif nxtpt == 0:
        sum += x
        break
    # nxtpt > 0
    m = pt + l*b
    ddprint("m {}".format(m))
    if m>=0:
        sum += b - (m)//l
    else:
        m = -m
        sum += b + (m+u-1)//u
    break

print(sum)

Submission status: Wrong Answer

Solution code:
N,X=map(int,input().split())
L=[]
for i in range(N):
  a,b,c=map(int,input().split())
  L.append([a,b,c,a*b,a*b+(X-a)*c])
L.sort(key=lambda x:x[4],reverse=True)
C=sum(L[i][3] for i in range(N))
ans=0
i=0
while C and i<N:
  if C>=L[i][4]:
    C-=L[i][4]
    ans+=X
  else:
    T=[]
    for j in range(i,N):
      if C<=L[j][3]:
        s=C//L[j][1]      
        s+=1 if C%L[j][1]!=0 else 0
        T.append(s)
      else:
        D=C-L[j][3]
        s=D//L[j][2]
        s+=1 if D%L[j][2]!=0 else 0
        T.append(s+L[j][0])
    ans+=min(T)
    break
  i+=1
print(ans)

Submission status: Wrong Answer

Solution code:
def getlist():
	return map(int, input().split())

T = 0
N, X = getlist()
L = []

for i in range(N):
	b, l, u = getlist()
	L.append([(X - b) * u, l, u, b])
	T += b * l

L = sorted(L)


ans = 0
for i in range(len(L)):
	l = L[-1 - i][1]
	u = L[-1 - i][2]
	b = L[-1 - i][3]
	if T >= X * u - b * (u - l):
		ans += X
		T -= X * u - b * (u - l)
	else:
		val = float("inf")
		for j in range(N - i):
			ll = L[j][1]
			if T % ll == 0:
				ans1 = int(T // ll)
			else:
				ans1 = int(T // ll) + 1
			if ans1 < val:
				val = ans1

		if (T + b * (u - l)) % u == 0:
			ans2 = int((T + b * (u - l)) // u)
		else:
			ans2 = int((T + b * (u - l)) // u) + 1
		ans += min(val, ans2)
		break

print(ans)

Submission status: Wrong Answer

Solution code:
n,c=map(int,input().split())
d=[list(map(int,input().split()))for i in range(n)]
b=0
for i in d:
    b+=i[0]*i[1]
s=sorted(d,key=lambda x:(x[0]-c)*x[2])
g=0
e=0
for i in range(n):
    if b+(s[i][2]-s[i][1])*s[i][0]>=g+s[i][2]*c:
        b+=(s[i][2]-s[i][1])*s[i][0]
        g+=s[i][2]*c
        e+=c
    else:
        t=sorted(s[i:],key=lambda x:-x[1])
        print(min(e+(b+(s[i][2]-s[i][1])*s[i][0]-g-1)//s[i][2]+1,e+(b-g-1)//t[0][1]+1))
        exit()

Submission status: Wrong Answer

Solution code:
n,c=map(int,input().split())
d=[list(map(int,input().split()))for i in range(n)]
b=0
for i in d:
    b+=i[0]*i[1]
s=sorted(d,key=lambda x:(x[0]-c)*x[2])
g=0
e=0
for i in range(n):
    if b+(s[i][2]-s[i][1])*s[i][0]>g+s[i][2]*c:
        b+=(s[i][2]-s[i][1])*s[i][0]
        g+=s[i][2]*c
        e+=c
    else:
        t=sorted(s[i:],key=lambda x:-x[1])
        print(min(e+(b+(s[i][2]-s[i][1])*s[i][0]-g-1)//s[i][2]+1,e+(b-g-1)//t[0][1]+1))
        exit()

Submission status: Wrong Answer

Solution code:
def getlist():
	return map(int, input().split())

T = 0
N, X = getlist()
L = []

for i in range(N):
	b, l, u = getlist()
	L.append([(X - b) * u, l, u, b])
	T += b * l

L = sorted(L)


ans = 0
for i in range(len(L)):
	l = L[-1 - i][1]
	u = L[-1 - i][2]
	b = L[-1 - i][3]
	if T >= X * u - b * (u - l):
		ans += X
		T -= X * u - b * (u - l)
	else:
		val = float("inf")
		for j in range(N - i - 1):
			ll = L[j][1]
			if T % ll == 0:
				ans1 = int(T // ll)
			else:
				ans1 = int(T // ll) + 1
			if ans1 < val:
				val = ans1

		if (T + b * (u - l)) % u == 0:
			ans2 = int((T + b * (u - l)) // u)
		else:
			ans2 = int((T + b * (u - l)) // u) + 1
		ans += min(val, ans2)
		break

print(ans)

Submission status: Wrong Answer

Solution code:
import math
inpl = lambda: list(map(int,input().split()))
N, X = inpl()
BLU = []
goal = 0
for _ in range(N):
    b, l ,u = inpl()
    p = b*l + (X-b)*u
    BLU.append([b,l,u,p])
    goal += b * l

BLU.sort(key=lambda x: -x[3])
i = 0
while i < N and goal >= BLU[i][3]:
    goal -= BLU[i][3]
    i += 1
ans = X*i
last = X
for j in range(i,N):
    b, l, u, p = BLU[j]
    if b*l >= goal:
        cur_last = int(math.ceil(goal / l))
    else:
        cur_last = int(math.ceil((goal - b*l)/u)) + b
    if cur_last < last:
        last = cur_last

ans += last
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
import numpy as np
np.set_printoptions(suppress=True)
# n = int(input())
# a, b = map(int, input().split())
# int_list = list(map(int, input().split()))
# l = list(input().split())


debug = True
debug = False


def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    n, x = map(int, input().split())
    # b_list = []
    # l_list = []
    # u_list = []
    # b, l, u, eff
    data = np.zeros(shape=(n, 6))

    # eff_list = []
    for i in range(n):
        b, l, u = map(int, input().split())
        base_minus = b * l # 重み最低でむべんの場合の負け点
        max_plus = (x-b) * u # 重み最高で満点の時の勝ち点
        eff = max_plus + base_minus # 重み最高にした時の勉強効率（最高勝ちと基本負けの差額）
        data[i] = [b, l, u, eff, max_plus, base_minus]

    eff_argsort = np.argsort(data[:, 3])[::-1]
    dprint(data[eff_argsort])

    total_time = 0
    total_score = -1*np.sum(data[:, 5]) # 負け点の合計
    dprint(total_score)

    import math
    for i in range(n):
        d = data[eff_argsort][i]
        # b = d[0]
        # l = d[1]
        # u = d[2]
        # eff = d[3]
        # max_plus = d[4]
        # base_minus = d[5]

        total_score_tmp = total_score
        if total_score < 0:
            total_score_tmp += d[3]

        # まだ勉強が足りない
        if total_score_tmp < 0:
            # コミットして勉強を続ける
            total_score = total_score_tmp
            total_time += x
            dprint(i, total_score, total_time)
        else:
            # これを全力すると勉強しすぎの場合
            # 残り必要点数を稼ぐのにもっとも効率がいいものを探す
            dprint("ajusting")
            dprint(total_time, total_score)
            rest_data = data[i:] # 勝負が済んでいないテスト
            dprint(rest_data)
            rest_time = (-1*total_score - rest_data[:, 5]) / rest_data[:, 2] + rest_data[:, 0] # 残り点数を埋めるのに必要な時間のリスト
            dprint(rest_time)
            total_time += math.ceil(min(rest_time))

            break

    print(int(total_time))


solve()

Submission status: Wrong Answer

Solution code:
N,X = list(map(int,input().split()))

q = []
for i in range(N):
  q +=[list(map(int,input().split()))]

q.sort(key = lambda x: -(x[2]))

s = sum([i*j for i,j,k in q])

cum = 0
cnt = 0
import math
for i,j,k in q:
  if math.ceil((s - cum +(k-j)*i) / k) <= X:
    print(cnt + math.ceil((s - cum +(k-j)*i) / k))
    quit()
  else:
    cum += k*X
    s += (k-j)*i
    cnt += X
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
N, X = map(int, input().split())

test_list = []

aoki_target = 0

for i in range(N):
    b, l, u = map(int, input().split())
    test_list.append([(u * X - u * b + l * b), b, l, u])
    aoki_target += b * l

test_list = sorted(test_list, key=lambda x: x[0], reverse=True)

ans = 0
takahashi = 0

for test in test_list:
    b = test[1]
    l = test[2]
    u = test[3]
    if takahashi + u * X < aoki_target + (u - l) * b:
        ans += X
        takahashi += X * u
        aoki_target += (u - l) * b
    else:
        aoki_target2 = aoki_target + (u - l) * b
        ans += min((aoki_target2 - takahashi + u - 1) // u,(aoki_target - takahashi + l - 1) // l)
        break

print(ans)

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
blu=[]
l=[]
s=0
for i in range(n):
    a=[int(j) for j in input().split()]
    blu.append([a[0],a[1],a[2],a[0]*a[1],a[0]*a[2],(x-a[0])*a[2]])
    s+=a[0]*a[1]
    
from operator import itemgetter
blu.sort(key=itemgetter(5))
blu.reverse()
ans=0

for i in range(n):
    if s+blu[i][0]*(blu[i][2]-blu[i][1])-x*blu[i][2]>0:
        ans+=x
        s+=blu[i][0]*(blu[i][2]-blu[i][1])-x*blu[i][2]
        
    else:
        import math
        y=(s+blu[i][0]*(blu[i][2]-blu[i][1]))/blu[i][2]
        ans+=math.ceil(y)
        break

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

n,x = [int(i) for i in input().split()]
#b=[0]*n
#l=[0]*n
#u=[0]*n
blu = [[int(i) for i in input().split()] for j in range(n)]
blu.sort(key = lambda y: y[0]*y[1]+(x-y[0])*y[2], reverse = True)

ans = 0
ao=0
ten = 0

m=x
tmp=0
for i in range(n):
    ao += blu[i][0] * blu[i][1]
ok=1
#print(blu,ao)
for b,l,u in blu:
    if ao - l*b > ten + u*(x-b) and ok:
        ao -= l*b
        ten += u*(x-b)
        ans += x
    else:
#        print(ao,ten,b,l,u,ans)
        ok = 0
        if ao-l*b <= ten:
            tmp = (ao-ten+(l-1))//l
        else:
            tmp = b + (ao-ten-l*b+(u-1))//u
#            print(ao-ten-l*b)
    
        if m > tmp:
            m=tmp

if ok == 0:
    print(ans+m)
else:
    print(ans)

Submission status: Wrong Answer

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

N, X = map(int, input().split())
blu = [list(map(int, input().split())) for _ in range(N)]

def mydivup(a, b): return (a + b - 1) // b

blu.sort(key=lambda x:  -(x[2] * (X - x[0])) )

loss_tab = [(bi * li) for bi, li, ui in blu]

ans = 0
loss_tmp = sum(loss_tab)
for i, (bi, li, ui) in enumerate(blu):
    tak_best = (X - bi) * ui
    loss_tmp -= loss_tab[i]
    if tak_best >= loss_tmp:
        i_end = i
        loss_tmp += loss_tab[i]
        break
    else:
        ans += X
        loss_tmp -= tak_best
        # print("#", (bi, li, ui), tak_best, X, loss_tmp)

ans_tmp = X
for i, (bi, li, ui) in enumerate(blu):
    if i < i_end: continue
    ans_tmp2 = bi + mydivup(loss_tmp - loss_tab[i], ui)
    # print("##", (bi, li, ui), ans_tmp2)
    if ans_tmp > ans_tmp2:
        ans_tmp = ans_tmp2

ans += ans_tmp
# print("#", sum([bi for bi, li, ui in blu]))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import groupby

N,X = list(map(int, input().split()))
BLU = [list(map(int, input().split())) for _ in range(N)]

NEED_POINT = sum([b*l for b,l,u in BLU])

max_points = [(b*l + (X-b)*u,b,l,u) for b,l,u in BLU]

ans = 10**15
for i in range(N):
  temp_ans = 0
  need_point = NEED_POINT
  M = max_points[:i] + max_points[i+1:]
  M.sort(reverse=True, key=lambda x:x[0])
  
  for m in M:
    if need_point >= m[0]:
      need_point -= m[0]
      temp_ans += X
    else:
      break

  m,b,l,u = max_points[i]
  if b*l >= need_point:
    temp_ans += (need_point+l-1)//l
  else:
    temp_ans += b + ((need_point-b*l)+u-1)//u
  ans = min(ans, temp_ans)

      
print(ans)

Submission status: Wrong Answer

Solution code:
import math

def main():
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    X = int(buflist[1])
    iblu = []
    for i in range(N):
        buf = input()
        buflist = buf.split()
        iblu.append((i, int(buflist[0]), int(buflist[1]), int(buflist[2])))
    aoki_score = 0
    takahashi_score = 0
    for x in iblu:
        aoki_score += x[1] * x[2]
    score_gain = []
    for x in iblu:
        score_gain.append((x[0], X * x[3] - x[1] * (x[3] - x[2])))
    score_gain.sort(reverse=True, key=lambda x: x[1])
    end = 0
    new_takahashi_score = 0
    for i, x in enumerate(score_gain):
        new_takahashi_score += x[1]
        if new_takahashi_score >= aoki_score:
            end = i
            break
    new_takahashi_score = 0
    study_hour = 0
    for i, x in enumerate(score_gain):
        new_takahashi_score = takahashi_score + x[1]
        if new_takahashi_score < aoki_score:
            study_hour += X
            takahashi_score = new_takahashi_score
        else: # new_takahashi_score >= aoki_score
            smm = X
            for k in range(end+1):
                score_needed = aoki_score - takahashi_score
                study_minimum = X
                for j in range(k):
                    penalty = iblu[score_gain[j][0]][1] * (iblu[score_gain[j][0]][3] - iblu[score_gain[j][0]][2])
                    st = min(math.ceil(score_needed / iblu[score_gain[j][0]][2]), math.ceil((score_needed + penalty) / iblu[score_gain[j][0]][3]))
                    if st < study_minimum:
                        study_minimum = st
                for j in range(i+k, N):
                    penalty = iblu[score_gain[j][0]][1] * (iblu[score_gain[j][0]][3] - iblu[score_gain[j][0]][2])
                    st = min(math.ceil(score_needed / iblu[score_gain[j][0]][2]), math.ceil((score_needed + penalty) / iblu[score_gain[j][0]][3]))
                    if st < study_minimum:
                        study_minimum = st
                if study_minimum < smm:
                    smm = study_minimum
                if i+k >= N:
                    break
                takahashi_score += score_gain[i+k][1] - score_gain[k][1]
            #penalty = iblu[x[0]][1] * (iblu[x[0]][3] - iblu[x[0]][2])
            #study_hour += min(math.ceil(score_needed / iblu[x[0]][2]), math.ceil((score_needed + penalty) / iblu[x[0]][3]))
            #takahashi_score += iblu[x[0]][2] * math.ceil(score_needed / iblu[x[0]][2]) if math.ceil(score_needed / iblu[x[0]][2]) < math.ceil((score_needed + penalty) / iblu[x[0]][3]) else iblu[x[0]][3] * math.ceil((score_needed + penalty) / iblu[x[0]][3]) - penalty
            study_hour += smm
            takahashi_score = aoki_score
        if takahashi_score >= aoki_score:
            break
    print(study_hour)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
import numpy as np
np.set_printoptions(suppress=True)
# n = int(input())
# a, b = map(int, input().split())
# int_list = list(map(int, input().split()))
# l = list(input().split())


debug = True
#debug = False


def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    n, x = map(int, input().split())
    # b_list = []
    # l_list = []
    # u_list = []
    # b, l, u, eff
    data = np.zeros(shape=(n, 6))

    # eff_list = []
    for i in range(n):
        b, l, u = map(int, input().split())
        base_minus = b * l # 重み最低でむべんの場合の負け点
        max_plus = (x-b) * u # 重み最高で満点の時の勝ち点
        eff = max_plus + base_minus # 重み最高にした時の勉強効率（最高勝ちと基本負けの差額）
        data[i] = [b, l, u, eff, max_plus, base_minus]

    eff_argsort = np.argsort(data[:, 3])[::-1]
    dprint(data[eff_argsort])

    total_time = 0
    total_score = -1*np.sum(data[:, 5]) # 負け点の合計
    dprint(total_score)

    import math
    for i in range(n):
        d = data[eff_argsort][i]
        # b = d[0]
        # l = d[1]
        # u = d[2]
        # eff = d[3]
        # max_plus = d[4]
        # base_minus = d[5]

        total_score_tmp = total_score
        if total_score < 0:
            total_score_tmp += d[3]

        # まだ勉強が足りない
        if total_score_tmp < 0:
            # コミットして勉強を続ける
            total_score = total_score_tmp
            total_time += x
            dprint(i, total_score, total_time)
        else:
            # これを全力すると勉強しすぎの場合
            # 残り必要点数を稼ぐのにもっとも効率がいいものを探す
            dprint("ajusting")
            dprint(total_time, total_score)
            rest_data = data[i:] # 勝負が済んでいないテスト
            dprint(rest_data)
            rest_time = (-1*total_score - rest_data[:, 5]) / rest_data[:, 2] + rest_data[:, 0] # 残り点数を埋めるのに必要な時間のリスト
            dprint(rest_time)
            total_time += math.ceil(min(rest_time))
            break

    print(int(total_time))


solve()

Submission status: Wrong Answer

Solution code:
import math
n, x = map(int, input().split())
blu = [list(map(int, input().split())) for _ in range(n)]
f = lambda y:(x-y[0])*y[2]+y[1]*y[0]
blu = sorted(blu, key = f, reverse = True)
B = 0
for i in range(n):
    b, l, u = blu[i]
    B+=b*l
i=0
ans = 0
while True:
    tmp = f(blu[i])
    if B>tmp:
        B-=tmp
        ans+=x
    else:
        break
    i+=1
k=x
B-=f(blu[i])
ans+=x
List = sorted(blu[:i+1], key = lambda x:x[2])
ans -= (-B)//List[0][2]
print(ans)

Submission status: Wrong Answer

Solution code:
N, X = map(int, input().split())

data = []
sum_score = 0
for _ in range(N):
	b, l, u = map(int, input().split())
	data.append((-(l * (X - b) + u * b), (b, l, u)))
	sum_score += b

count = len(data)
data.sort()
data = [values for _, values in data]

def check(h):
	score = 0
	for i in range(count):
		h_use = min(h, X)
		b, l, u = data[i]
		if h_use > b:
			score += u * (h_use - b)
		else:
			score += u * (h_use - b)
		h -= h_use
		i += 1
	
	return score

h_min = 0
h_max = sum_score
while h_min < h_max:
	h = (h_max + h_min) // 2
	score = check(h)
	
	if score >= 0:
		h_max = h
	else:
		h_min = h + 1

print(h_min)

Submission status: Wrong Answer

Solution code:
import sys, math, collections, heapq, itertools
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    file = sys.stdin.readline
    N, X = map(int, file().split())
    aoki = [None] * N
    for i in range(N):
        b, l, u = map(int, file().split())
        aoki[i] = [u,  l, -b]
    aoki.sort()
    low = [0] * (N + 1)
    high = [0] * (N + 1)
    takahashi = [0] * (N + 1)
    for i in range(N):
        low[i+1] = low[i] + aoki[i][2] *  (-1) * aoki[i][1]
        high[i+1] = high[i] + aoki[i][0]  * (-1) * aoki[i][2]
        takahashi[i+1] = takahashi[i] + aoki[i][0] * X

    minhour = X * N
    tmult = 1
    for i in range(1, N):
        S = low[i] + high[N] - high[i]
        tpoint = takahashi[N] - takahashi[i]
        tmult = max(tmult, aoki[i-1][1])
        if tpoint >= S:
            over = min(X, (tpoint - S) // aoki[i][0])
            minhour = min(minhour, X * (N - i) - over)
        else:
            extra = 0
            if math.ceil((S -tpoint) / tmult) > X: break
            else: extra = math.ceil((S - tpoint) / tmult)
            minhour = min(minhour, X * (N - i) + extra)
    print(minhour)

    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N,X = list(map(int,input().split()))

q = []
for i in range(N):
  q +=[list(map(int,input().split()))]

q.sort(key = lambda x: -(X -x[0])*(x[2]))

s = sum([i*j for i,j,k in q])

cum = 0
cnt = 0
import math
for i,j,k in q:
  if math.ceil((s - cum +(k-j)*i) / k) <= X:
    print(cnt + math.ceil((s - cum +(k-j)*i) / k))
    quit()
  else:
    cum += k*X
    s += (k-j)*i
    cnt += X
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from math import ceil 
n,x=map(int,input().split())
A=[]
for i in range(n):
  b,l,u=map(int,input().split())
  tp = u * (x - b)
  ap = l * b
  A.append([abs(ap-tp),b,l,u])
A.sort(reverse=True)
asum=0
AP=[[0,0]]
for i in range(n):
  AP.append([AP[-1][0]+A[i][1]*A[i][2],AP[-1][1]+A[i][1]*A[i][3]])

APS=[AP[-1][0]]
for i in range(n):
  APS.append(APS[-1]+AP[i][1]-AP[i][0])
APS=APS[::-1]
APS=[APS[0]]+APS
tsum=0
ans=0

for i in range(n):
  if APS[i] - tsum <= x * A[i][3]:
    print(ans+ceil((APS[i]-tsum)/A[i][2]))
    break
  else:
    tsum+=x*A[i][3]
    ans+=x

Submission status: Wrong Answer

Solution code:
import bisect


n, x = map(int, input().split())
tests = []
targets = []
low_costs = []
need_point = 0
for i in range(n):
    b, l, u = map(int, input().split())
    tests.append((b, l, u))
    targets.append((u*x-(u-l)*b, i))
    low_costs.append((b, -u, (-(u*x-(u-l)*b), i)))
    need_point += l*b
targets.sort(reverse=True)
low_costs.sort()

if n == 1:
    print(tests[0][0])
    exit()

ranks = [0]*n

total_cost = 0
total_point = 0
point_sum = []
for i in range(n):
    # 何番目に大きいかを記録
    ranks[targets[i][1]] = i
    total_point += targets[i][0]
    total_cost += x
    point_sum.append(total_point)


def want_n_point(n, b, l, u):
    if n/l < b:
        return (n+l-1)//l
    else:
        m = n + (u-l)*b
        return (m + u - 1)//u


j = bisect.bisect_right(point_sum, need_point)
if j == 0:
    min_cost = float('inf')
    for i in range(n):
        b,l,u = tests[i]
        cost = want_n_point(need_point, b,l,u)
        min_cost = min(min_cost, cost)
    print(min_cost)
    exit()
if j == n:
    print(n*x)
    exit()
        
if point_sum[j] == need_point:
    min_cost = x * j
else:
    min_cost = x*(j+1)


# print('need: ', need_point)
# print('point_sum:', point_sum)
# print('min_cost', min_cost)

for i in range(n):
    r = ranks[i]
    b, l, u = tests[i]
    max_point = u*x - (u-l)*b

    # ps=[10, 100, 200], max_point=50, need_point(120)
    # 120-50 = 70はj=1の位置に挿入される大きさ。
    # j番目までの合計(100)にmax_point(50)を足すとneed_point(120)を超える
    j = bisect.bisect_right(point_sum, need_point-max_point)
    husoku = need_point - point_sum[j]

    # print('max_point:', max_point)
    # print('j:', j)
    if r <= j:
        # ほんまか？
        # print(r, i,'***continue***')
        continue
    # print('husoku', husoku)
    # print('(j+1)*x:', (j+1)*x)
    # print('want_n_point(husoku, b, l, u)',want_n_point(husoku, b, l, u))
    cost = (j+1)*x + want_n_point(husoku, b, l, u)
    min_cost = min(min_cost, cost)
    # print(r, i, cost, min_cost)

print(min_cost)

Submission status: Wrong Answer

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

n,x = inm()
blu = []
pt = 0
for i in range(n):
    b,l,u = inm()
    v = u - (u-l)*b/x
    blu.append((v,b,l,u))
    pt -= l*b
blu.sort(reverse=True)

sum = 0
for z in blu:
    v,b,l,u = z
    nxtpt = pt + l*b + u*(x-b)
    if nxtpt < 0:
        pt = nxtpt
        sum += x
        continue
    elif nxtpt == 0:
        sum += x
        break
    # nxtpt > 0
    m = pt + l*b
    if m>=0:
        sum += b - (m-l+1)//l
    else:
        m = -m
        sum += b + (m-u+1)//u
    break

print(sum)

Submission status: Wrong Answer

Solution code:
n,c=map(int,input().split())
d=[list(map(int,input().split()))for i in range(n)]
b=0
for i in d:
    b+=i[0]*i[1]
s=sorted(d,key=lambda x:(x[0]-c)*x[2])
g=0
e=0
for i in range(n):
    if b+(s[i][2]-s[i][1])*s[i][0]>g+s[i][2]*c:
        b+=(s[i][2]-s[i][1])*s[i][0]
        g+=s[i][2]*c
        e+=c
    else:
        r,k=e,e
        tom=g
        t=sorted(s[i:],key=lambda x:-x[1])
        for j in range(len(t)):
            if b>g+t[j][0]*t[j][1]:
                g+=t[j][0]*t[j][1]
                r+=t[j][0]
            else:
                r+=(b-g-1)//t[j][1]+1
                break
        else:
            print(min(k+(b+(s[i][2]-s[i][1])*s[i][0]-tom-1)//s[i][2]+1,r))
            exit()