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: Runtime Error

Solution code:
from itertools import accumulate
n,x = map(int,input().split())
blr = [list(map(int,input().split())) for i in range(n)]
tad = []
for i in range(n):
  b,l,r = blr[i]
  tad.append(((x-b)*r+b*l,-b*l,(x-b)*r,i))
tad.sort(reverse=True)
t = list(zip(*tad))[2]
a = list(zip(*tad))[1]
a = [a[i]*(-1) for i in range(n)]
tacc = list(accumulate(t))
aacc = list(accumulate(a))
for i in range(n):
  if tacc[i]>=aacc[n-1]-aacc[i]:
    p = i
    break
if p == 0:
  tsum = 0
  asum = aacc[n-1]
else:
  tsum = tacc[p-1]
  asum = aacc[n-1]-aacc[p-1]
vis = [0]*n
for i in range(p):
  if tad[i][0] == tad[p][0]:
    continue
  v = tad[i][3]
  vis[v] = 1
ans = 10**18
flg = 0
for i in range(n):
  if vis[i]:
    continue
  b,l,r = blr[i]
  asumd = asum-b*l
  dif = tsum-asumd
  anstmp = p*x
  if dif >= 0:
    anstmp += b-dif//l
  else:
    anstmp += (-dif+r-1)//r+b
  if anstmp > (p+1)*x:
    continue
  if dif >= 0 and anstmp < ans:
    flg = 1
  elif anstmp < ans:
    flg = 0
  ans = min(ans,anstmp)
if flg:
  print(2/0)
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
n,x = map(int,input().split())
blr = [list(map(int,input().split())) for i in range(n)]
tad = []
for i in range(n):
  b,l,r = blr[i]
  tad.append(((x-b)*r+b*l,-b*l,(x-b)*r,i))
tad.sort(reverse=True)
t = list(zip(*tad))[2]
a = list(zip(*tad))[1]
a = [a[i]*(-1) for i in range(n)]
tacc = list(accumulate(t))
aacc = list(accumulate(a))
for i in range(n):
  if tacc[i]>=aacc[n-1]-aacc[i]:
    p = i
    break
if p == 0:
  tsum = 0
  asum = aacc[n-1]
else:
  tsum = tacc[p-1]
  asum = aacc[n-1]-aacc[p-1]
vis = [0]*n
for i in range(p):
  if tad[i][0] == tad[p][0]:
    continue
  v = tad[i][3]
  vis[v] = 1
ans = 10**18
for i in range(n):
  if vis[i]:
    continue
  b,l,r = blr[i]
  asumd = asum-b*l
  dif = tsum-asumd
  anstmp = p*x
  if dif >= 0:
    anstmp += b-dif//l
    print(2/0)
  else:
    anstmp += (-dif+r-1)//r+b
  if anstmp > (p+1)*x:
    continue
  ans = min(ans,anstmp)
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
n,x = map(int,input().split())
blr = [list(map(int,input().split())) for i in range(n)]
tad = []
for i in range(n):
  b,l,r = blr[i]
  tad.append(((x-b)*r+b*l,-b*l,(x-b)*r,i))
tad.sort(reverse=True)
t = list(zip(*tad))[2]
a = list(zip(*tad))[1]
a = [a[i]*(-1) for i in range(n)]
tacc = list(accumulate(t))
aacc = list(accumulate(a))
for i in range(n):
  if tacc[i]>=aacc[n-1]-aacc[i]:
    p = i
    break
if p == 0:
  tsum = 0
  asum = aacc[n-1]
else:
  tsum = tacc[p-1]
  asum = aacc[n-1]-aacc[p-1]
vis = [0]*n
for i in range(p):
  if tad[i][0] == tad[p][0]:
    continue
  v = tad[i][3]
  vis[v] = 1
ans = 10**18
for i in range(n):
  if vis[i]:
    continue
  b,l,r = blr[i]
  asumd = asum-b*l
  dif = tsum-asumd
  anstmp = p*x
  if dif >= 0:
    anstmp += b-dif//l
  else:
    anstmp += (-dif+r-1)//r+b
    print(2/0)
  if anstmp > (p+1)*x:
    continue
  ans = min(ans,anstmp)
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
n,x = map(int,input().split())
blr = [list(map(int,input().split())) for i in range(n)]
tad = []
for i in range(n):
  b,l,r = blr[i]
  tad.append(((x-b)*r+b*l,-b*l,(x-b)*r,i))
tad.sort(reverse=True)
t = list(zip(*tad))[2]
a = list(zip(*tad))[1]
a = [a[i]*(-1) for i in range(n)]
tacc = list(accumulate(t))
aacc = list(accumulate(a))
for i in range(n):
  if tacc[i]>=aacc[n-1]-aacc[i]:
    p = i
    break
if p == 0:
  tsum = 0
  asum = aacc[n-1]
else:
  tsum = tacc[p-1]
  asum = aacc[n-1]-aacc[p-1]
vis = [0]*n
if p == 0:
  print(2/0)
for i in range(p):
  if tad[i][0] == tad[p][0]:
    continue
  v = tad[i][3]
  vis[v] = 1
ans = 10**18
for i in range(n):
  if vis[i]:
    continue
  b,l,r = blr[i]
  asumd = asum-b*l
  dif = tsum-asumd
  anstmp = p*x
  if dif >= 0:
    anstmp += b-dif//l
  else:
    anstmp += (-dif+r-1)//r+b
  if anstmp > (p+1)*x:
    continue
  ans = min(ans,anstmp)
print(ans)

Submission status: Runtime Error

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 goal >= BLU[i][3]:
    goal -= BLU[i][3]
    i += 1
ans = X*i
if goal == 0:
    last = 0
elif goal == 1:
    last = 1
else:
    last = X
    p0 = BLU[i][3]
    tmp_goal = goal - p0
    for j in range(N):
        b, l, u, p = BLU[j]
        if p > p0:
            goal = tmp_goal + p
        else:
            goal = tmp_goal + p0
        if p < goal:
            break
        elif 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
            if last == 1:
                break
ans += last
print(ans)

Submission status: Runtime Error

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
k, prev_p = 0, 10**12
while goal >= BLU[i][3]:
    goal -= BLU[i][3]
    i += 1
    if BLU[i][3] < prev_p:
        k = 0
        prev_p = BLU[i][3]
    else:
        k += 1
ans = X*i
if goal == 0:
    last = 0
elif goal == 1:
    last = 1
else:
    if BLU[i][3] < prev_p:
        k = 0
    last = X
    for j in range(i-k,N):
        b, l, u, p = BLU[j]
        if p < goal:
            break
        elif 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
            if last == 1:
                break

ans += last
print(ans)

Submission status: Runtime Error

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
k, prev_p = 0, 10**12
while goal >= BLU[i][3]:
    goal -= BLU[i][3]
    i += 1
    if BLU[i][3] < prev_p:
        k = 0
        prev_p = BLU[i][3]
    else:
        k += 1
ans = X*i
if goal == 0:
    last = 0
elif goal == 1:
    last = 1
else:
    last = X
    for j in range(i-k,N):
        b, l, u, p = BLU[j]
        if p < goal:
            break
        elif 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
            if last == 1:
                break

ans += last
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Jun  3 22:07:34 2019

@author: Yamazaki Kenichi
"""

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

D = 0
S = []
for c in blu:
    D += c[0] * c[1]
    S.append([c[0], c[1], c[2], c[0] * c[1] + (X - c[0]) * c[2]])

S.sort(reverse=True, key = lambda x: x[3])
Ss = [0,S[0][3]]
for i in range(1,N):
    Ss.append(Ss[-1] + S[i][3])

def a(blu, a):
    b, l, u = blu[0], blu[1], blu[2]
    if a <= b:
        return a * l
    else:
        return b * l + (a - b) * u

i = N * X // 2
le, re = 0, N * X + 1
while re - le != 1:
    cmpl_n = i // X
    incmpl = i % X 
    efficent = 0
    for j in range(N):
        if j < cmpl_n:
            tmp = Ss[cmpl_n + 1]
            tmp -= S[j][3]
            tmp += a(S[j][:3], incmpl)
        else:
            tmp = Ss[cmpl_n]
            tmp += a(S[j][:3], incmpl)
        efficent = max(tmp, efficent)
#        print(efficent,le,i,re,j,cmpl_n,incmpl,tmp)
    if re - le == 1:
        break
    if efficent - D >= 0:
        le, i, re = le, (le + i)// 2, i
    elif efficent - D < 0:
        le, i, re = i, (i + re)// 2, re

if efficent - D > 0:
    print(i)
else:
    print(i + 1)

Submission status: Runtime Error

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 goal >= BLU[i][3]:
    goal -= BLU[i][3]
    i += 1
ans = X*i
if goal == 0:
    pass
elif goal == 1:
    last = 1
else:
    last = X
    for j in range(i,N):
        b, l, u, p = BLU[j]
        if p < goal:
            break
        elif 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
            if last == 1:
                break

ans += last
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
import heapq
 
 
def solve(N: int, X: int, b: "List[int]", l: "List[int]", u: "List[int]"):
 
    # i番目のテストで高橋くんがx点とったとき、A-Bに加える量
    def f(i, x):
        if x <= b[i]:
            return l[i]*(x-b[i])
        else:
            return u[i]*(x-b[i])
 
    # あらかじめ、0点とった時とX点とった時の効果が大きい順に並べておく
    mh = [[f(i, X)-f(i, 0), i] for i in range(N)]
    mh.sort(reverse=True)
 
    def isOK(index, key):
        # 勉強時間Tとしてスコア(A-B)を最大化するよう勉強時間を配分する
        T = index
        num = -(-T//X)          # 点をとるテストの個数
        # いったんX点とらせる
        D = sum([f(i, X) for _, i in mh[:num]])\
            + sum([f(i, 0) for _, i in mh[num:]])
        # 点を取るテストの中で、点数をT%X点に変更した時、
        # 最も減少の小さいものを選ぶ
        v, i = min([[f(i, X)-f(i, T % X), i] for _, i in mh[:num]])
        D += -v
        return D >= key
 
    def binary_search(key):
        ng = -1
        ok = N*X
        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            if isOK(mid, key):
                ok = mid
            else:
                ng = mid
        return ok
 
    ans = binary_search(0)
    print(ans)
    return
 
 
def main():
 
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    b = [int()] * (N)  # type: "List[int]"
    l = [int()] * (N)  # type: "List[int]"
    u = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        b[i] = int(next(tokens))
        l[i] = int(next(tokens))
        u[i] = int(next(tokens))
    solve(N, X, b, l, u)
 
 
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
import heapq


def solve(N: int, X: int, b: "List[int]", l: "List[int]", u: "List[int]"):

    # i番目のテストで高橋くんがx点とったとき、A-Bに加える量
    def f(i, x):
        if x <= b[i]:
            return l[i]*(x-b[i])
        else:
            return u[i]*(x-b[i])

    # あらかじめ、0点とった時とX点とった時の効果が大きい順に並べておく
    mh = [[f(i, X)-f(i, 0), i] for i in range(N)]
    mh.sort(reverse=True)

    def isOK(index, key):
        # 勉強時間Tとしてスコア(A-B)を最大化するよう勉強時間を配分する
        T = index
        num = -(-T//X)          # 点をとるテストの個数
        # いったんX点とらせる
        D = sum([f(i, X) for _, i in mh[:num]])\
            + sum([f(i, 0) for _, i in mh[num:]])
        # 点を取るテストの中で、点数をT%X点に変更した時、
        # 最も減少の小さいものを選ぶ
        v, i = min([[f(i, X)-f(i, T % X), i] for _, i in mh[:num]])
        D += -v
        return D >= key

    def binary_search(key):
        ng = -1
        ok = N*X
        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            if isOK(mid, key):
                ok = mid
            else:
                ng = mid
        return ok

    ans = binary_search(0)
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    b = [int()] * (N)  # type: "List[int]"
    l = [int()] * (N)  # type: "List[int]"
    u = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        b[i] = int(next(tokens))
        l[i] = int(next(tokens))
        u[i] = int(next(tokens))
    solve(N, X, b, l, u)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys,heapq,time
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()
    s = u*(x-b) + l*b
    v = s/x
    t = x
    heapq.heappush(blu, (-v,s,t,b,l,u))
    pt -= l*b

sum = 0
while len(blu)>0:
    mv,s,t,b,l,u = heapq.heappop(blu)
    nxtpt = pt + s
    ddprint("v {} b {} l {} u {} pt {} nx {} sum {}".format(-mv,b,l,u,pt,nxtpt,sum))
    if nxtpt < 0:
        pt = nxtpt
        sum += t
        continue
    elif nxtpt == 0:
        print(sum+t)
        exit()
    else:  # nxtpt > 0
        m = pt + l*b
        ddprint("m {}".format(m))
        if m>=0:
            t = (-pt+l-1)//l
            #t = b - (m)//l
            #if t==0:
            #    print('6')
            #    exit()
        else:
            m = -m
            t = b + (m+u-1)//u
            #if t==0:
            #    time.sleep(8)
        s = -pt
        heapq.heappush(blu, (-s/t,s,t,b,l,u))

Submission status: Runtime Error

Solution code:
import sys,heapq,time
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()
    s = u*(x-b) + l*b
    v = s/x
    t = x
    heapq.heappush(blu, (-v,s,t,b,l,u))
    pt -= l*b

sum = 0
while len(blu)>0:
    mv,s,t,b,l,u = heapq.heappop(blu)
    nxtpt = pt + s
    ddprint("v {} b {} l {} u {} pt {} nx {} sum {}".format(v,b,l,u,pt,nxtpt,sum))
    if nxtpt < 0:
        pt = nxtpt
        sum += t
        continue
    elif nxtpt == 0:
        print(sum+t)
        exit()
    else:  # nxtpt > 0
        m = pt + l*b
        ddprint("m {}".format(m))
        if m>=0:
            t = b - (m)//l
            if DBG and t==0:
                print('6')
                exit()
        else:
            m = -m
            t = b + (m+u-1)//u
            if DBG and t==0:
                time.sleep(8)
        s = -pt
        heapq.heappush(blu, (-s/t,s,t,b,l,u))

Submission status: Runtime Error

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()
    s = u*(x-b) + l*b
    v = s/x
    t = x
    heapq.heappush(blu, (-v,s,t,b,l,u))
    pt -= l*b

sum = 0
while len(blu)>0:
    mv,s,t,b,l,u = heapq.heappop(blu)
    nxtpt = pt + s
    ddprint("v {} b {} l {} u {} pt {} nx {} sum {}".format(v,b,l,u,pt,nxtpt,sum))
    if nxtpt < 0:
        pt = nxtpt
        sum += t
        continue
    elif nxtpt == 0:
        print(sum+t)
        exit()
    else:  # nxtpt > 0
        m = pt + l*b
        ddprint("m {}".format(m))
        if m>=0:
            t = b - (m)//l
        else:
            m = -m
            t = b + (m+u-1)//u
        s = -pt
        heapq.heappush(blu, (-s/t,s,t,b,l,u))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun  2 20:33:46 2019

@author: Yamazaki Kenichi
"""

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

for i in range(N):
    blu[i] += [(X - blu[i][0]) * blu[i][2] + blu[i][0] * blu[i][1]]

blu.sort(reverse=True, key = lambda x: x[3])

Aoki = []
for c in blu:
    Aoki += [c[0]*c[1]]
AS = sum(Aoki)

ans = 0
i = 0
while i < N:
#    if AS - Aoki[i] - blu[i][3] < 0:
    if AS - blu[i][6] < 0:
        break
    else:
#        AS -= (Aoki[i] + blu[i][3])
        AS -= blu[i][3]
        ans += X
        i += 1
#    print(i,ans,AS,blu[i])

#ans += (((AS - Aoki[i] - 1)//blu[i][2] + 1) + blu[i][0])
tmp = X + 50
for j in range(i,N):
    tmp = min((((AS - Aoki[j] - 1)//blu[j][2] + 1) + blu[j][0]), tmp)
    print(j,tmp,(((AS - Aoki[j] - 1)//blu[j][2] + 1) + blu[j][0]))
ans += tmp

print(ans)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<utility>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<queue>
#include<set>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define prin(arg) std::cout<<arg<<"\n"
#define prin2(arg1,arg2) std::cout<<arg1<<" "<<arg2<<"\n"
#define fill(arg,n) std::memset(arg,n,sizeof(arg))
#define mp std::make_pair
#define pb push_back
using std::cin;
typedef long long ll;
typedef std::pair<int,int> pi;
typedef std::pair<ll,ll> pll;
typedef std::pair<ll,pll> plll;
typedef std::vector<int> vi;
typedef std::set<int> si;
typedef std::string str;
const int INF=1e+9;
const ll INFLL=1e+17;
const ll MOD=1e+9+7;
int N;
ll X;
ll B[100010],L[100010],U[100010];
plll p[100010];
ll Y;
bool comp1(plll& a,plll& b){
  ll ab=a.first,al=a.second.first,au=a.second.second;
  ll bb=b.first,bl=b.second.first,bu=b.second.second;  
  return (X-ab)*au+ab*al>(X-bb)*bu+bb*bl;
}
bool comp2(plll& a,plll& b){
  ll ab=a.first,al=a.second.first,au=a.second.second;
  ll bb=b.first,bl=b.second.first,bu=b.second.second;  
  return ab*al<bb*bl;
}

bool C(ll mid){
  ll tkhs=0,aok=0;
  rep(i,N){
    ll b=p[i].first,l=p[i].second.first,u=p[i].second.second;
    if(mid>=X){
      tkhs+=X*u;aok+=b*u;
      mid-=X;
    }
    else if(mid!=0){
      if(mid>b){
	tkhs+=mid*u;aok+=b*u;
      }
      else{
	//	std::sort(p+i,p+N,comp2);
	//	b=p[i].first;l=p[i].second.first;u=p[i].second.second;                  
	tkhs+=mid*l;aok+=b*l;
      }
      mid=0;
    }
    else{
      aok+=b*l;
    }
  }
  return tkhs>=aok;
}
ll upper(ll l,ll r){//条件を満たす中で最小のものを返す
  ll lb=l-1,ub=r+1;
  while(ub-lb>1){
    std::sort(p,p+N,comp1);
    ll mid=(lb+ub)/2;
    if(C(mid)) ub=mid;
    else lb=mid;
  }
  return ub;
}


int main(){
  cin>>N>>X;
  ll sum=0;
  rep(i,N){
    cin>>B[i]>>L[i]>>U[i];
    sum+=B[i];
  }
  rep(i,N){
    p[i]=mp(B[i],mp(L[i],U[i]));
  }
  ll res=upper(0,sum);
  prin(res);
  
  return 0;
}

Submission status: Runtime Error

Solution code:
n,x = map(int,input().split())
base_score  =0
my_score = 0
ans = 0
b = []
l = []
u = []
sco = []
for i in range(n):
    ba,la,ua = map(int,input().split())
    b.append(ba)
    l.append(la)
    u.append(ua)
    sco.append([ba,la,ua])
    base_score += ba*la

#print(base_score)
for i in range(n):
    sco[i].append((x*sco[i][2])-(sco[i][0]*(sco[i][2]-sco[i][1])))

sco = sorted(sco, key = lambda a: a[3] )

while my_score<=base_score:
    k = base_score - my_score
    if k <= sco[-1][3]:
        i = -1

        while (sco[i][3] >=k and -i <len(sco)):
            i = i-1
        nom = sco[-1][1]
        lob = 0
        for s in range(i,-1):
            nom = max(sco[s][1],nom)
            lob = s
        if ((k-1)//nom)+1 < x:
            ans += ((k-1)//nom)+1
            my_score = base_score+1
        else:
            ans += x
            my_score += nom*x
            sco.pop(lob)

    else:
        my_score += sco[-1][3]
        ans += x
        sco.pop(-1)


print(ans)

Submission status: Runtime Error

Solution code:
n,x = map(int,input().split())
base_score  =0
my_score = 0
ans = 0
b = []
l = []
u = []
sco = []
for i in range(n):
    ba,la,ua = map(int,input().split())
    b.append(ba)
    l.append(la)
    u.append(ua)
    sco.append([ba,la,ua])
    base_score += ba*la

#print(base_score)
for i in range(n):
    sco[i].append((x*sco[i][2])-(sco[i][0]*(sco[i][2]-sco[i][1])))

sco = sorted(sco, key = lambda a: a[3] )

while my_score<=base_score:
    k = base_score - my_score
    if k <= sco[-1][3]:
        i = -1

        while (sco[i][3] >=k and -i <len(sco)):
            i = i-1
        nom = sco[-1][1]
        for s in range(i,-1):
            nom = max(sco[s][1],nom)
        if ((k-1)//nom)+1 < x:
            ans += ((k-1)//nom)+1
            my_score = base_score+1
        else:
            ans += x
            my_score += nom*x
            sco.pop(-s)

    else:
        my_score += sco[-1][3]
        ans += x
        sco.pop(-1)


print(ans)

Submission status: Runtime Error

Solution code:
n,x=map(int,input().split())
d=[]
dx=[]
bpoint=0
for i in range(n):
    a,b,c=map(float,input().split())
    d.append((a,b,c))
    bpoint+=a*b
    b,c=b/a,c/a
    dx.append((a,b,c,c-b,i))

dx=sorted(dx,key=lambda x:-x[3])
apoint=0
time=0
print(bpoint)
for i in range(n):
    apoint+=d[dx[i][4]][2]*x
    bpoint+=(d[dx[i][4]][2]-d[dx[i][4]][1])*d[dx[i][4]][0]
    if apoint<bpoint:
        time+=x
    else:
        if apoint==bpoint:
            time+=x
            print(time)
            break
        else:
            apoint-=d[dx[i][4]][2]*x
            for k in range(x+1):
                apoint+=d[dx[i][4]][2]*1
                if apoint>=bpoint:
                    time+=k
                    print(time)
                    exit()

Submission status: Runtime Error

Solution code:
from operator import itemgetter
import math
n,x = map(int, input().split())
bl = [0]
blu = [list(map(int, input().split())) for i in range(n)]
blu.sort(key = itemgetter(2), reverse = True)
ans = 0
for key,i in enumerate(blu):
    b,l,u = i[0],i[1],i[2]
    bl.append(bl[0]+b*l)
for key,i in enumerate(blu):
    b, l, u = i[0], i[1], i[2]
    res = bl[-1] - bl[i+1]
    a = (x - b) * u
    if ans + a >= res:
        ans += math.ceil(res / u)
        break
    else:
        now += a
print(ans)

Submission status: Runtime Error

Solution code:
def get(list,n):
    sum=0
    a=[]
    for i in range(len(list)):
        sum+=list[i][0]*list[i][1]
        a.append([(n-list[i][0])*list[i][2],i])
    a.sort()
    i,z=0,True
    count=0
   
    a.reverse()
   
    while i<len(a) and z:
        sum-=(100*list[a[i][1]][2])
        count+=100
        
        if sum<0:
              z=False
        else:
              i+=1
   
    sum+=100*list[a[i][1]][2]
    count-=100
    if sum%(list[a[i][1]][2])==0:
            count+=sum//list[a[i][1]][2]
    else:
        count+=sum//(list[a[i][1]][2]+1)
    return count
m=list(map(int,input().strip().split()))
l=[]
for i in range(m[0]):
    l.append(list(map(int,input().strip().split())))
print(get(l,m[1]))

Submission status: Runtime Error

Solution code:
n,x = map(int,input().split())
base_score  =0
my_score = 0
ans = 0
b = []
l = []
u = []
sco = []
for i in range(n):
    ba,la,ua = map(int,input().split())
    b.append(ba)
    l.append(la)
    u.append(ua)
    sco.append([ba,la,ua])
    base_score += ba*la

#print(base_score)
for i in range(n):
    sco[i].append((x*sco[i][2])-(sco[i][0]*(sco[i][2]-sco[i][1])))

sco = sorted(sco, key = lambda a: a[3] )

while my_score<=base_score:
    k = base_score - my_score
    if k <= sco[-1][3]:
        i = -1

        while (sco[i][3] >=k and -i <len(sco)):
            i = i-1
        nom = sco[-1][1]
        for s in range(i,-1):
            nom = max(sco[s][1],nom)
        if ((k-1)//nom)+1 < x:
            ans += ((k-1)//nom)+1
            my_score = base_score+1
        else:
            ans += x
            my_score += nom*x
            sco.pop(-i)

    else:
        my_score += sco[-1][3]
        ans += x
        sco.pop(-1)


print(ans)

Submission status: Runtime Error

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]
g = lambda x:x-(B+(x-x[0])*x[2])/u[1]-b[0]
List = sorted(blu[:i+1], key = lambda x:x-(B+(x-x[0])*x[2])/u[1]-b[0])
ans=min(ans+(-B)//List[0][2]-g(List[0]), ans)
print(ans)

Submission status: Runtime Error

Solution code:
class Kenken():
	def __init__(self,n,a,b,c,d,s):
		self.n = n
		self.a = a-1
		self.b = b-1
		self.c = c-1
		self.d = d-1
		self.s = s
		self.s = self.s[:a-1] + "A" + self.s[a:]
		self.s = self.s[:b-1] + "B" + self.s[b:]

	def str_replace(self,i,k,S):
		if k == 1:
			self.s = self.s[:i] + "." + S + self.s[i+2:]
		else:
			self.s = self.s[:i] + "." + self.s[i+1] + S + self.s[i+3:]

	def check_stone(self,i):
		if i < self.n:
			if self.s[i] == ".":
				return True
		return False

	def check_goal(self):
		if self.a == self.c and self.b == self.d:
			return False
		else:
			return True

	def left(self,target,i):
		if target == "a":
			self.str_replace(self.a,i,"A")
			self.a += i
		else:
			self.str_replace(self.b,i,"B")
			self.b += i
	
	def get_space(self,S):
		if S == "a":
			return self.a
		elif S == "b":
			return self.b
		elif S == "c":
			return self.c
		elif S == "d":
			return self.d

	def print_all(self):
		print(self.s)

n,a,b,c,d = map(int, input().split())
s = input()

ken = Kenken(n,a,b,c,d,s)
flag=0
ken.print_all()
while ken.check_goal():
	if (ken.check_stone(ken.get_space("b")+1) and ken.check_stone(ken.get_space("b")-1)) or (ken.get_space("a")+1 == ken.get_space("b") and ken.check_stone(ken.get_space("b")+1)): 
		if ken.check_stone(ken.get_space("a")+1) and ken.get_space("a") != ken.get_space("c"):
			ken.left("a",1)
		elif ken.check_stone(ken.get_space("a")+2) and ken.get_space("a") != ken.get_space("c"):
			ken.left("a",2)
		elif ken.check_stone(ken.get_space("b")+1) and ken.get_space("b") != ken.get_space("d"):
			ken.left("b",1)
		elif ken.check_stone(ken.get_space("b")+2) and ken.get_space("b") != ken.get_space("d"):
			ken.left("b",2)
		else:
			flag=1
			break
	else:
		if ken.check_stone(ken.get_space("b")+1) and ken.get_space("b") != ken.get_space("d"):
			ken.left("b",1)
		elif ken.check_stone(ken.get_space("b")+2) and ken.get_space("b") != ken.get_space("d"):
			ken.left("b",2)
		elif ken.check_stone(ken.get_space("a")+1) and ken.get_space("a") != ken.get_space("c"):
			ken.left("a",1)
		elif ken.check_stone(ken.get_space("a")+2) and ken.get_space("a") != ken.get_space("c"):
			ken.left("a",2)
		else:
			flag=1
			break
	ken.print_all()

if flag == 0:
	print("Yes")
else:
	print("No")

Submission status: Runtime Error

Solution code:
n, x = [int(item) for item in input().strip().split(" ")]
import math
from itertools import accumulate
import sys
import numpy as np
ks = []
bls = []
bus = []
ps = []
bs = []
ls = []
us = []
for line in sys.stdin:
    b,l,u = [int(i) for i in line.strip().split(" ")]
    ks.append((x - b) * u)
    bls.append(b*l)
    bus.append(b*u)
    ps.append(u*x)

    bs.append(b)
    ls.append(l)
    us.append(u)

bls = np.array(bls)
bus = np.array(bus)
ps = np.array(ps)

bs = np.array(bs)
ls = np.array(ls)
us = np.array(us)



idx = np.argsort(ks)[::-1]

bls = bls[idx]
bus = bus[idx]
ps = ps[idx]

bs = bs[idx]
ls = ls[idx]
us = us[idx]

bls = list(accumulate(bls))
bus = list(accumulate(bus))
ps = list(accumulate(ps))
for i in range(n):
    if bus[i] + (bls[-1] - bls[i]) < ps[i]:
        ri = i
        if i != 0:
            B = bus[i-1] + (bls[-1] - bls[i])
            P = ps[i-1]
        else:
            B = bls[-1] - bls[i]
            P = 0
        break
# ri is ok
t = ri * x
b, l, u = bs[i], ls[i], us[i]
mint = None
for i in range(u-l+1):
    x = l+i
    mm = math.ceil(float(b * x + B - P) / x)
    if mint == None:
        mint = mm
    else:
        mint = min(mm, mint)
print(t+mint)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N, X = map(int, input().split())

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


test.sort(key = lambda x: x[1])
ascend = [test[i][3] for i in range(N)]
test.sort(key = lambda x: x[2], reverse = True)
descend = [test[i][3] for i in range(N)]

test.sort(key = lambda x: x[3])

a = 0
d = 0
remain = 0

while test[ascend[a]][1] < test[descend[d]][2]:
    if test[ascend[a]][0] == 0:
        a += 1
        continue
    if test[descend[d]][0] == X:
        d += 1
        continue

    if test[ascend[a]][1] * test[ascend[a]][0] + remain < test[descend[d]][2]*(X-test[descend[d]][0]):
        plus = (test[ascend[a]][1]*test[ascend[a]][0]+remain) // test[descend[d]][2]
        remain = (test[ascend[a]][1]*test[ascend[a]][0]+remain) % test[descend[d]][2]
        test[descend[d]][0] += plus
        test[ascend[a]][0] = 0
        a += 1

    elif test[ascend[a]][1] * test[ascend[a]][0] + remain == test[descend[d]][2]*(X-test[descend[d]][0]):
        test[descend[d]][0] = X
        test[ascend[a]][0] = 0
        a += 1
        d += 1

    else:
        ukeire = test[descend[d]][2]*(X-test[descend[d]][0]) - remain
        test[descend[d]][0] = X
        plus = (ukeire-1) // test[ascend[a]][1] + 1
        test[ascend[a]][0] -= plus
        remain = plus*test[ascend[a]][1] - ukeire
        d += 1

    if a >= N or d >= N:
        break

ans = 0
for i in range(N):
    ans += test[i][0]
print(ans)