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:
from operator import itemgetter
N, X = map(int, input().split())
S = [list(map(int, input().split())) for i in range(N)]
A = []
aoki = 0
for i, (b, l, u) in enumerate(S):
    A.append([(X-b)*u + (b)*l, i])
    aoki += b*l
A.sort(reverse=True, key=itemgetter(0))
ans = 0
tak = 0
for iaaaa, (a, i) in enumerate(A):
    if aoki >= a:
        aoki -= a
        ans += X
        if aoki==0:
            print(ans)
            exit()
    else:
        break
mi = float("inf")
aoki_ = aoki
for j in range(iaaaa, N):
    a, i = A[j]
    b, l, u = S[i]
    aoki = aoki_
    an, m = divmod(aoki, l)
    if m!=0:
        an += 1
    mi = min(mi, an)
    aoki += (u-l) * b
    an, m = divmod(aoki, u)
    if m!=0:
        an += 1
    mi = min(mi, an)
ans_ = ans + mi

a, i = A[iaaaa]
aoki_ -= a
aoki_ = -aoki
anss = (iaaaa+1)*X
ma = 0
for a, i in A[:iaaaa]:
    b, l, u = S[i]
    aoki = aoki_

    an, m = divmod(aoki, u)
    ma = max(ma, an)

    an = X-b
    aoki -= (u-l)*an

    an, m = divmod(aoki, l)
    ma = max(ma, an)


print(min(ans_, anss-ma))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    N, X = get_li()
    B, L, U = get_data(N, [int, int, int])
    A = [0] * N
    P = deque(sorted(range(N), key=lambda i: U[i] * (X - B[i])))
    Q = deque(sorted(range(N), key=lambda i: L[i]))
    total = sum((0 - b) * c for b, c in zip(B, L))
    time = 0
    all = set(range(N))
    worked = set()
    while True:
        p = P.pop()
        if total + (L[p] - U[p]) * B[p] + U[p] * X >= 0:
            break
        total += (L[p] - U[p]) * B[p] + U[p] * X
        time += X
        worked.add(p)
    p = min(all - worked, key=lambda i: min((L[i] - 1 - total) // L[i], (U[i] - 1 - total + (U[i] - L[i]) * B[i]) // U[i]))
    time += min((L[p] - 1 - total) // L[p], (U[p] - 1 - total + (U[p] - L[p]) * B[p]) // U[p])
    print(time)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N, X = map(int, input().split())
S = [list(map(int, input().split())) for i in range(N)]
A = []
aoki = 0
for i, (b, l, u) in enumerate(S):
    A.append([(X-b)*u + (b)*l, i])
    aoki += b*l
A.sort(reverse=True, key=itemgetter(0))
ans = 0
tak = 0
for iaaaa, (a, i) in enumerate(A):
    if aoki >= a:
        aoki -= a
        ans += X
        if aoki==0:
            print(ans)
            exit()
    else:
        break
mi = float("inf")
aoki_ = aoki
for j in range(iaaaa, N):
    a, i = A[j]
    b, l, u = S[i]
    aoki = aoki_
    an, m = divmod(aoki, l)
    if m!=0:
        an += 1
    mi = min(mi, an)
    aoki += (u-l) * b
    an, m = divmod(aoki, u)
    if m!=0:
        an += 1
    mi = min(mi, an)
ans_ = ans + mi

a, i = A[iaaaa]
aoki_ -= a
aoki_ = -aoki
anss = (iaaaa+1)*X
ma = 0
for a, i in A[:iaaaa]:
    b, l, u = S[i]
    aoki = aoki_

    an, m = divmod(aoki, u)
    ma = max(ma, an)

    an = X-b
    aoki -= (u-l)*an

    if aoki < 0:
        continue

    an, m = divmod(aoki, l)
    ma = max(ma, an)


print(min(ans_, anss-ma))

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])
    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
            score_needed = aoki_score - takahashi_score
            study_minimum = X
            for j in range(i, 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
            #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 += study_minimum
            takahashi_score = new_takahashi_score
        if takahashi_score >= aoki_score:
            break
    print(study_hour)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

ans = 0

N, X = map(int,input().split())
inList = []
temp_lost = 0

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

inList.sort(key=lambda x: -x[3])
for i in range(N):
  if(temp_lost <0 and (temp_lost+inList[i][3]) > 0 ):
    if( (-temp_lost) > inList[i][0]*inList[i][1]):
      # win is needed
      ans += min(math.ceil((0-temp_lost)/inList[i][2]), inList[i][0])
    else:
      # lost is allowed
      ans += math.ceil((0-temp_lost)/inList[i][1])
    break
  else:
    ans += X
    temp_lost += inList[i][3]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N, X = map(int, input().split())
BLU = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
B, L, U = map(list, zip(*BLU))
C = [(u-l)*b for b, l, u in BLU]
D = [(X*u - c, u, c, l) for u, c, l in zip(U, C, L)]
D.sort(reverse = True)
SL = sum(l*b for l, b in zip(L, B))
SS = 0
for i, (d, _, _, _) in enumerate(D):
    SS += d
    if SS >= SL:
        break
SSb = SS - d
lans = i*X
m = 10**10
for _, u, c, l in D[i:]:
    m = min(m, -(-(c + SL - SSb)//u), -((SSb - SL)//l))
lans += m

ans = (i+1) * X
m = 0
for _, u, _, _ in D[:i+1]:
    m = max(m, (SS - SL)//u)
print(min(lans, ans - m))

Submission status: Wrong Answer

Solution code:
from math import ceil

n,x = map(int,input().split())
#v = list(map(int,input().split()))
tlist = []
for i in range(n):
    b,l,u = map(int,input().split())
    tlist.append([b,l,u,i])

ans = 0

cp = []
#calc コスパ
for i in tlist:
    cp.append(i[2]*x-(i[2]-i[1])*i[0])

leastline = 0
for i in tlist:
    leastline += i[0]*i[1]

#tlistをコスパで並び替え
#cptlistord = sorted(range(len(cp)) key=lambda x: cp[x])
cplist = sorted(tlist, key=lambda x: cp[x[3]])[::-1]

#print(cplist)
nowleastline = leastline
lenc = len(cplist)
for _ in range(lenc):
    i = cplist[0]
    leastline = nowleastline
    nowleastline = nowleastline + (i[2] - i[1])*i[0] - x*i[2]
    if nowleastline <= 0:
        break
    else:
        ans += x
        del cplist[0]

hokan1 = cplist[0]

cplist = sorted(cplist, key=lambda x: x[1])[::-1]
hokan2 = cplist[0]


#print(ceil((leastline+(hokan1[2] - hokan1[1])*hokan1[0])/hokan1[2]))
#print(ceil(leastline/hokan2[1]))

ans += min(ceil((leastline+(hokan1[2] - hokan1[1])*hokan1[0])/hokan1[2]),ceil(leastline/hokan2[1]))

print(ans)

Submission status: Wrong Answer

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

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

data=sorted(data,key=lambda x:x[3],reverse=True)

S=[-l_sum]
s=-l_sum
for i in range(N):
    s += data[i][3]
    S.append(s)

def judge(P):

    n=P//X
    p=P%X

    if S[n]>=0:
        return True
    else:
        new_list = []
        for i in range(N):
            if i>=n:
                b,l,u,x = data[i]
                if p>=b:
                    new_list.append(u*(p-b)+l*b)
                else:
                    new_list.append(l*p)
            else:
                b,l,u,x = data[i]
                new_list.append(max(u*(p-X),l*p-u*X+b*(u-l))+data[n][3])
                
        if S[n] + max(new_list)>=0:
            return True
        else:
            return False

max_P=N*X

def bisect(m,M):
    if M-m==1:
        return M
    else:
        if judge((m+M)//2):
            return bisect(m,(m+M)//2)
        else:
            return bisect((m+M)//2,M)

print(bisect(0,max_P))

Submission status: Wrong Answer

Solution code:
import math
N, X = map(int, input().split())
B = []
L = []
U = []
for i in range(N):
  b,l,u = map(int, input().split())
  B += [b]
  L += [l]
  U += [u]

behind = 0
for i in range(N):
  behind += L[i]*B[i]
  
gain_max = [(max(X*U[i] - B[i]*(U[i]-L[i]),X*L[i]),i) for i in range(N)]
studied = [0 for i in range(N)]
ans = 0

gain_max.sort()
takahashi_score = 0
while takahashi_score < behind:
  if takahashi_score + gain_max[-1][0] < behind:
    ans += X
    gain = gain_max.pop(-1)
    takahashi_score += gain[0]
    studied[gain[1]] = 1
  else:#残り１科目で勝てる！
    curr = X
    for i in range(N):
      if studied[i] == 0:
        curr = min(curr,min((behind - takahashi_score - B[i]*L[i])/U[i]+B[i],
                  (behind - takahashi_score - B[i]*L[i])/L[i]+B[i]))
    ans += math.ceil(curr)
    break
        
print(ans)

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
for j in range(i, n):
    b, l, u = blu[j]
    k = min(math.ceil(B/l), math.ceil((B+(u-l)*b)/l), k)
print(ans+k)

Submission status: Wrong Answer

Solution code:
import math
INF = 10**12
n, x = [int(item) for item in input().split()]
blu = [[int(item) for item in input().split()] for _ in range(n)]

manten_point = []
loosing_point = 0 
for i, (b, l, u) in enumerate(blu):
    manten_point.append([(x-b) * u + b * l, i])
    loosing_point += b * l 

manten_point.sort(reverse=True)

manten_set = set() 
for p, index in manten_point:
    if loosing_point < p:
        break
    loosing_point -= p
    manten_set.add(index)

r_time = INF 
# R senryaku
for i, (b, l, u) in enumerate(blu):
    if i in manten_set:
        continue
    if (x-b) * u + b * l >= loosing_point:
        val = int(math.ceil((loosing_point - b*l) / u)) + b
    else:
        val = INF
    r_time = min(r_time, val)

# L senryaku
l_rate_set = [0] * (10**5 + 1)
l_time = 0
for i, (b, l, u) in enumerate(blu):
    if i in manten_set:
        continue
    l_rate_set[l] += b
for i in range(10**5, -1, -1):
    if loosing_point < l_rate_set[i] * i:
        l_time += int(math.ceil(loosing_point / i))
        break
    else:
        loosing_point -= l_rate_set[i] * i
        l_time += l_rate_set[i]

print(min(l_time, r_time) + len(manten_set) * x)

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])
    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
            score_needed = aoki_score - takahashi_score
            minimum_study = X
            for j in range(iblu[x[0]][2], iblu[x[0]][3]+1):
                penalty = iblu[x[0]][1] * (j - iblu[x[0]][2])
                st = math.ceil((score_needed + penalty) / j)
                if st < minimum_study:
                    minimum_study = st
            #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 += minimum_study
            takahashi_score = new_takahashi_score
        if takahashi_score >= aoki_score:
            break
    print(study_hour)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, x = [int(i) for i in input().split()]
B = [[int(i) for i in input().split()] for j in range(n)]

S = 0

for b, l, r in B:
    S -= b * l

B.sort(reverse=True, key=lambda b:(x - b[0]) * b[2])
ans = 0

for b, l, r in B:
    if S + x * r - b * (r - l) >= 0:
        ng = 0
        ok = x
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if S + mid * r - b * (r - l) >= 0:
                ok = mid
            else:
                ng = mid
        ans += ok
        break
    S += x * r - b * (r - l)
    ans += x

print(ans)

Submission status: Wrong Answer

Solution code:
n, x = [int(i) for i in input().split()]
B = [[int(i) for i in input().split()] for j in range(n)]

S = 0

for b, l, r in B:
    S -= b * l

B.sort(reverse=True, key=lambda b:x * b[2] - b[0] * (b[2] - b[1]))
ans = 0

for b, l, r in B:
    if S + x * r - b * (r - l) >= 0:
        ng = 0
        ok = x
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if S + mid * r - b * (r - l) >= 0:
                ok = mid
            else:
                ng = mid
        ans += ok
        break
    S += x * r - b * (r - l)
    ans += x

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N,X =[int(i)for i in input().split()]
lis = [[int(i)for i in input().split()]for _ in range(N)]#BLU
wa = 0
lis2 = []
index = []
for (b,l,u) in lis:
    G = (X-b)*u
    L = l*b
    n = bisect.bisect_left(index,G+L)
    lis2.insert(n,[G,L,b,l,u])
    index.insert(n,G+L)
ans = 0
lisp =[]
lism = [0,0,0,10**9,10**9]
s =False
for i in range(N):
    if wa <= 0:
        lisp =lis2.pop(-1)
        wa += lisp[0]
        ans += X
    else:
        lism =lis2.pop(0)
        wa -= lism[1]
    if i == N-1 and wa < 0:
        wa += lism[1]
        ans += lism[2]
        s = True
foo = min(wa//lisp[4],X-lisp[2])
bar = min(wa//lism[3],lism[2])
if not s:
    bar = 0
print(ans - max(foo,bar))

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
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(b,l,u)
        ok = 0
        if ao-l*b <= ten:
            tmp = (ao-ten+(l-1))//l
        else:
            tmp = b + (ao-ten-l*b+(u-1))//u
    
        if m > tmp:
            m=tmp

print(ans+m)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N, X = LI()
    li = []
    diff = 0
    for _ in range(N):
        b, l, u = LI()
        li.append([u * X - (u - l) * b, b, l, u])
        diff += l * b
    li.sort(reverse=True)
    ans = 0
    ans1 = INF
    flag = True
    for maxup, b, l, u in li:
        if flag and diff > maxup: # mada
            ans += X
            diff -= maxup
            continue
        flag = False
        # last win
        k = ((l - u) * b - diff) // u
        k = -k
        ans1 = min(ans1, k)
        # last lose
        k = -diff // l
        k = -k
        ans1 = min(ans1, k)
    ans += ans1
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
def inpl(): return list(map(int, input().split()))

input = sys.stdin.readline
N, X = inpl()
B = [0]*N
L = [0]*N
U = [0]*N

S = 0
K = []
for i in range(N):
    B[i], L[i], U[i] = inpl()
    S += B[i] * L[i]
    K.append(((X-B[i])*U[i], i))

K = sorted(K, key=itemgetter(0), reverse=True)

OK = N*X
NG = -1

def check(m):
    i = -1
    T = S*1
    div, mod = divmod(m, X)
    for i in range(div):
        g, j = K[i]
        T += -B[j]*L[j] - g

    for k in range(i+1, N):
        _, j = K[k]
        if mod <= B[j]:
            if T <= mod * L[j]:
                return True
        else:
            if T <= B[j]*L[j] + (mod - B[j])*U[j]:
                return True
    else:
        return False

while abs(OK-NG) > 1:
    mid = (OK+NG)//2
    if check(mid):
        OK = mid
    else:
        NG = mid

print(OK)

Submission status: Wrong Answer

Solution code:
s=input()
n = len(s)
cum = [0] * (n+1)
sr = s[::-1]
for i in range(n-1):
    if sr[i] == 'C' and sr[i+1] == 'B':
        cum[i+1] = cum[i] + 1
    elif sr[i] == 'A' or sr[i:i+2] in ['BC'] or (1 < i and sr[i-1:i+2] == 'CBA'):
        cum[i+1] = cum[i]
    else:
        cum[i+1] = 0
cum[n] = cum[n-1]
ans = 0
for i in range(n):
    if s[i] != 'A':
        continue
    ans += cum[n-i-1]

print(ans)

Submission status: Wrong Answer

Solution code:
import math
N,X = map(int, raw_input().split())
blu = []
summin = 0
count = 0
flag = 0
ss = []
for i in range(N):
	blu2 = map(int, raw_input().split())
	blu2.append(X*blu2[2]-blu2[0]*(blu2[2]-blu2[1]))
	summin += blu2[0]*blu2[1]
	blu.append(blu2)
blu = sorted(blu,key = lambda tup:(-tup[3]))
for temp in blu:
	if flag == 0:
		if(temp[3] < summin):
			summin -= temp[3]
			count += X
		else:
			flag = 1
			ss.append(min(math.ceil(summin/temp[1]),math.ceil((summin+temp[0]*(temp[2]-temp[1]))/temp[2])))
	else:
		ss.append(min(math.ceil(summin/temp[1]),math.ceil((summin+temp[0]*(temp[2]-temp[1]))/temp[2])))
if len(ss) != 0:
	print(count + int(min(ss)))
else:
	print(count)

Submission status: Wrong Answer

Solution code:
import math
INF = 10**12
n, x = [int(item) for item in input().split()]
blu = [[int(item) for item in input().split()] for _ in range(n)]

manten_point = []
loosing_point = 0 
for i, (b, l, u) in enumerate(blu):
    manten_point.append([(x-b) * u + b * l, i])
    loosing_point += b * l 

manten_point.sort(reverse=True)

manten_set = set() 
for p, index in manten_point:
    if loosing_point < p:
        break
    loosing_point -= p
    manten_set.add(index)

ans = INF 
# R senryaku, L senryaku
for i, (b, l, u) in enumerate(blu):
    if i in manten_set:
        continue
    if b*l >= loosing_point:
        val = int(math.ceil(loosing_point / l))
    elif (x-b) * u + b * l >= loosing_point:
        val = int(math.ceil((loosing_point - b*l) / u)) + b
    else:
        val = INF
    ans = min(ans, val)

print(ans + len(manten_set) * x)

Submission status: Wrong Answer

Solution code:
N,X = map(int,input().split())
BLU = [list(map(int,input().split())) for i in range(N)]
for i in range(N):
    b,l,u = BLU[i]
    BLU[i].append(u*X-(u-l)*b)
BLU.sort(key = lambda x:-x[3])

s = 0
for i in range(N):
    s -= BLU[i][1]*BLU[i][0]

ans = 0
for i in range(N):
    b,l,u,m = BLU[i]
    if s+m > 0:
        break
    s += m
    ans += X

BLU = BLU[i:]

from math import ceil
def solve(b,l,u,s):
    if u*X-(u-l)*b < s:
        return X
    if l*b >= s:
        return ceil(s/l)
    else:
        return ceil((s+b*(u-l))/u)

h = X
for b,l,u,m in BLU:
    h = min(h,solve(b,l,u,-s))

ans += h
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N, X = map(int, input().split())
S = [list(map(int, input().split())) for i in range(N)]
A = []
aoki = 0
for i, (b, l, u) in enumerate(S):
    A.append([(X-b)*u + (b)*l, i])
    aoki += b*l
A.sort(reverse=True, key=itemgetter(0))
ans = 0
tak = 0
for iaaaa, (a, i) in enumerate(A):
    if aoki >= a:
        aoki -= a
        ans += X
        if aoki==0:
            print(ans)
            exit()
    else:
        break
mi = float("inf")
aoki_ = aoki
for j in range(iaaaa, N):
    a, i = A[j]
    b, l, u = S[i]
    aoki = aoki_
    an, m = divmod(aoki, l)
    if m!=0:
        an += 1
    mi = min(mi, an)
    aoki += (u-l) * b
    an, m = divmod(aoki, u)
    if m!=0:
        an += 1
    mi = min(mi, an)
print(ans + mi)

Submission status: Wrong Answer

Solution code:
N,X=map(int,input().split())
above=[0]*N
under=[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)
    under[i]=(i,l*b)
    
    now-=l*b
above.sort(key=lambda x:x[1],reverse=True)
idx=0
used=set()
ans=0
while above[idx][1]+now<0:
    now+=above[idx][1]
    used|={above[idx][0]}
    idx+=1
    ans+=X
M=float('inf')
now*=-1
ansM=i
nowM=now
for i in range(N):
    if i in used:
        continue
    b,l,u=data[i]
    M0=(now+l-1)//l
    if M0>b:
        now0=now-l*b
        M0=b+(now0+u-1)//u
        if M0<=X and M0<M:
            M=M0
            ansM=i
            nowM=now0-(M0-b)*u
    elif M0<M:
        M=M0
        ansM=i
        nowM=now-M0*l
ans+=M
nowM*=-1
check=[data[i] for i in used|{ansM}]
check.sort(key=lambda x:x[2])
idx=0
while idx<len(check):
    if nowM-check[idx][2]>=0:
        nowM-=check[idx][2]
        ans-=1
    else:
        idx+=1
print(ans)

Submission status: Wrong Answer

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

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

q_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])
    score_needed += b * l

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

ans = 0

for i in range(N):
    if q_array[i][3] <= score_needed:
        ans += X
        score_needed -= q_array[i][3]
        if score_needed == 0:
            break
    else:
        study_min = X
        for j in range(i, N):
            b, l, u, s = q_array[j]
            if score_needed <= b * l:
                study_min = min(study_min, math.ceil(score_needed / l))
            else:
                study_min = min(study_min, b + math.ceil(
                    (score_needed - b * l) / u))
        ans += study_min
        break
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

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

b_list = [0]*N
l_list = [0]*N
u_list = [0]*N

for i in range(N):
    b, l, u = map(int, input().split())
    b_list[i] = b
    l_list[i] = l
    u_list[i] = u

# lose weight
lose_weight = sum([b_list[i]*l_list[i] for i in range(N)])

# win weight
win_weight = [(X - b_list[i])*u_list[i]+b_list[i]*l_list[i] for i in range(N)]

h = []
for i in range(N):
    heappush(h, (-win_weight[i], i))

used_flg = [0]*N
res = 0
while True:
    win, i = heappop(h)
    if win + lose_weight < 0:
        break
    elif win + lose_weight == 0:
        res += X
        used_flg[i] = 1
        lose_weight = 0
        break
    else:
        res += X
        used_flg[i] = 1
        lose_weight += win

r_min = X
for i in range(N):
    if used_flg[i] == 0:
        if lose_weight > b_list[i]*l_list[i]:
            p = lose_weight - b_list[i]*l_list[i]
            q = u_list[i]
            if p % q == 0:
                r = p // q + b_list[i]
            else:
                r = p // q + b_list[i] + 1
            if r < r_min:
                r_min = r
        else:
            p = lose_weight
            q = l_list[i]
            if p % q == 0:
                r = p // q
            else:
                r = p // q + 1
            if r < r_min:
                r_min = r

print(res + r_min)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N, X = LI()
    li = []
    diff = 0
    for _ in range(N):
        b, l, u = LI()
        li.append([u * (X - b), b, l, u])
        diff += l * b
    li.sort(reverse=True)
    ans = 0
    ans1 = INF
    flag = True
    for ma, b, l, u in li:
        tmp = diff - (ma + l * b)
        if flag and tmp > 0: # mada
            ans += X
            diff = tmp
            continue
        flag = False
        # last win
        k = ((l - u) * b - diff) // u
        k = -k
        ans1 = min(ans1, k)
        # last lose
        k = -diff // l
        k = -k
        ans1 = min(ans1, k)
    ans += ans1
    return ans

print(main())

Submission status: Wrong Answer

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

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

data=sorted(data,key=lambda x:x[3],reverse=True)

S=[-l_sum]
su=0
sl=l_sum
for i in range(N):
    b,l,u,x = data[i]
    su+=(X-b)*u
    sl-=b*l
    S.append(su-sl)

def judge(P):

    n=P//X
    p=P%X

    if S[n]>=0:
        return True
    else:
        new_list = []
        for i in range(n,N):
            b,l,u,x = data[i]
            if p>=b:
                new_list.append(u*(p-b)+l*b)
            else:
                new_list.append(l*p)
        if S[n] + max(new_list) >=0:
            return True
        else:
            return False

max_P=N*X

def bisect(m,M):
    if M-m==1:
        return M
    else:
        if judge((m+M)//2):
            return bisect(m,(m+M)//2)
        else:
            return bisect((m+M)//2,M)

print(bisect(0,max_P))

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])
    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
            score_needed = aoki_score - takahashi_score
            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
        if takahashi_score >= aoki_score:
            break
    print(study_hour)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

n, x = list(map(int, input().split()))
exams = []
norma = 0
for line in sys.stdin:
    b, l, u = map(int, line.split())
    exams.append((b * (u - l) - u * x, b * (l - u) / u, b, l, u))
    norma += b * l
# exams_sorted = sorted(exams)
exams_sorted = sorted(exams, reverse=True)
# print(exams_sorted)
# print(norma)

ans = 0
while -exams_sorted[-1][0] < norma:
    # print(f'norma:{norma}  d,b,l,u: {d},{b},{l},{u}  ans: {ans}')

    norma += exams_sorted.pop()[0]
    ans += x

extra = 10 ** 10
for d, _, b, l, u in exams_sorted:
    extra = min(extra, (norma - 1) // l + 1, (norma + b * (u - l) - 1) // u + 1)
ans += extra

print(ans)