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:
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

from itertools import combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def combinations_count(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(r))
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

# set the inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
    # R = lambda: list(map(int, input2().split()))
    # old_R = lambda: list(map(int, input().split()))
    # ex1) n, k = R()
    # ex2) v = list(R())
    # ex3) bc = [list(R()) for _ in range(m)]

# n, x =2, 100
# blu = [[85, 2, 3],[60, 1, 1]]

n, x = 10, 1000
blu = [[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]]

# input2 = sys.stdin.readline
# R = lambda: list(map(int, input2().split()))
# n, x = R()
# blu = [R() for _ in range(n)]

# calculate
tests = [(b * l + (x - b) * u, i) for i, (b, l, u) in enumerate(blu)]
tests.sort(reverse=True)
point_Aoki = sum([b * l for b, l, _ in blu])
point_Taka = 0
ans = 0
for i, test in enumerate(tests):
    if point_Taka + test[0] >= point_Aoki:
        ans += i * x
        num_break_Aoki = test[1]
        break
    point_Taka += test[0]

(b, l, u) = blu[num_break_Aoki]
if point_Taka + b*l >= point_Aoki:
    q, mod = divmod(point_Aoki - point_Taka,l)
    ans += q
    if mod != 0:
        ans += 1
else:
    point_Taka += b * l
    ans += b
    q, mod = divmod(point_Aoki - point_Taka,u)
    ans += q
    if mod != 0:
        ans += 1

# output
# ex1) print(*l) => when l = [2, 5], printed 2 5 6
print(ans)

Submission status: Wrong Answer

Solution code:
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

from itertools import combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def combinations_count(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(r))
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

# set the inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
    # R = lambda: list(map(int, input2().split()))
    # old_R = lambda: list(map(int, input().split()))
    # ex1) n, k = R()
    # ex2) v = list(R())
    # ex3) bc = [list(R()) for _ in range(m)]

# n, x =2, 100
# blu = [[85, 2, 3],[60, 1, 1]]

# n, x = 10, 1000
# blu = [[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]]

input2 = sys.stdin.readline
R = lambda: list(map(int, input2().split()))
n, x = R()
blu = [R() for _ in range(n)]

# calculate
tests = [(b * l + (x - b) * u, i) for i, (b, l, u) in enumerate(blu)]
tests.sort(reverse=True)
point_Aoki = sum([b * l for b, l, _ in blu])
point_Taka = 0
ans = 0
for i, test in enumerate(tests):
    if point_Taka + test[0] >= point_Aoki:
        ans += i * x
        num_break_Aoki = test[1]
        break
    point_Taka += test[0]

(b, l, u) = blu[num_break_Aoki]
if point_Taka + b*l >= point_Aoki:
    q, mod = divmod(point_Aoki - point_Taka,u)
    ans += q
    if mod != 0:
        ans += 1
else:
    point_Taka += b * l
    ans += b
    q, mod = divmod(point_Aoki - point_Taka,u)
    ans += q
    if mod != 0:
        ans += 1

# output
# ex1) print(*l) => when l = [2, 5], printed 2 5 6
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

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

b_total = 0
dblu = []
for b, l, u in blu :
    heappush(dblu, (-(u*X - (u-l)*b), b, l, u))
    b_total += b * l

ret = 0

while b_total > -dblu[0][0] :
    b_total += heappop(dblu)[0]
    ret += X

m = float('inf')
for _, b, l, u in dblu :
    if b_total <= b * l :
        m = min(m, -(-b_total // l))
    else :
        m = min(m, -(-(b_total - b * l) // u) + b)

print(ret + m)

Submission status: Wrong Answer

Solution code:
from math import ceil

n, x = map(int, input().split())
tests = [list(map(int, input().split())) for _ in range(n)]

need_points = 0

for i in range(n):
    b, l, u = tests[i]
    need_points += l * b
    negative_max_kiyo = -(l * b + u * (x - b))
    tests[i] = [negative_max_kiyo, l, u, b]

tests.sort()

ans = 0
additional_need_time = x
mode = 0
for negative_max_kiyo, l, u, b in tests:

    if mode == 0 and -negative_max_kiyo <= need_points:
        need_points += negative_max_kiyo
        ans += x
    elif need_points <= l * b:
        mode = 1
        additional_need_time = min(additional_need_time, ceil(need_points / l))
    else:
        mode = 1
        additional_need_time = min(
            additional_need_time, ceil((need_points - l * b) / u) + b
        )
ans += additional_need_time
print(int(ans))

Submission status: Wrong Answer

Solution code:
from math import ceil

n, x = map(int, input().split())
tests = [list(map(int, input().split())) for _ in range(n)]

need_points = 0

for i in range(n):
    b, l, u = tests[i]
    need_points += l * b
    negative_max_kiyo = -(l * b + u * (x - b))
    tests[i] = [negative_max_kiyo, l, u, b]

tests.sort()

ans = 0
additional_need_time = x
mode = 0
for negative_max_kiyo, l, u, b in tests:

    if mode == 0 and -negative_max_kiyo < need_points:
        need_points += negative_max_kiyo
        ans += x
    elif need_points <= l * b:
        mode = 1
        additional_need_time = min(additional_need_time, ceil(need_points / l))
    else:
        mode = 1
        additional_need_time = min(
            additional_need_time, ceil((need_points - l * b) / u) + b
        )
ans += additional_need_time
print(int(ans))

Submission status: Wrong Answer

Solution code:
def qScore(b, l, u):
    return u*(X-b) + l*b

def rScore(a, b, l, u):
    return (u*(a-b) + l*b if (a-b) > 0 else l*a)

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

blu = sorted([(x, qScore(*x)) for x in blu], key=(lambda x: x[1]), reverse=True)
A = sum(x[0][0] * x[0][1] for x in blu)

top_k = -1
A_dummy = A
for i, (_, s) in enumerate(blu):
    if A_dummy < s:
        break
    A_dummy -= s
    top_k = i
else:
    print(N * X)
    exit()

max_r = X-1
min_r = 0

mid_r = 0
while min_r <= max_r:
    mid_r = int(min_r + (max_r - min_r) / 2)
    for i in range(len(blu)):
        score = rScore(mid_r, *blu[i][0])
        if i <= top_k:
            A_check = A_dummy + blu[i][1] - blu[top_k + 1][1] - score
        else:
            A_check = A_dummy - score
        if A_check < 0:
            max_r = mid_r - 1
            break
        elif A_check == 0:
            max_r -= 1
            break
    else:
        min_r = mid_r + 1
print((top_k+1)*X + mid_r)

Submission status: Wrong Answer

Solution code:
from math import ceil

n, x = map(int, input().split())
tests = [list(map(int, input().split())) for _ in range(n)]

need_points = 0

for i in range(n):
    b, l, u = tests[i]
    need_points += l * b
    negative_max_kiyo = -(l * b + u * (x - b))
    tests[i] = [negative_max_kiyo, l, u, b]

tests.sort()

ans = 0
additional_need_time = x
mode = 0
for negative_max_kiyo, l, u, b in tests:

    if mode == 0 and -negative_max_kiyo < need_points:
        need_points += negative_max_kiyo
        ans += x
    elif need_points <= l * b:
        mode = 1
        additional_need_time = min(additional_need_time, ceil(need_points / l))
    else:
        mode = 1
        additional_need_time = min(
            additional_need_time, ceil((need_points - l * b) / u) + b
        )
ans += additional_need_time
print(ans)

Submission status: Wrong Answer

Solution code:
def qScore(b, l, u):
    return u*(X-b) + l*b

def rScore(a, b, l, u):
    return (u*(a-b) + l*b if (a - b) > 0 else l*a)

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

blu = [(x, qScore(*x)) for x in blu]
blu = sorted(blu, key=(lambda x: x[1]), reverse=True)
A = sum(x[0][0] * x[0][1] for x in blu)

max_k = sum(x[0][0] for x in blu)
min_k = min(x[0][0] for x in blu)

k = 0
while min_k <= max_k:
    k = (max_k + min_k) // 2
    q = k // X
    r = k - q * X
    for i in range(len(blu)):
        score = rScore(r, *blu[i][0])
        if (i <= q) and (q > 0):
            score += sum(x[1] for x in blu[:i])
            score += sum([x[1] for x in blu[i+1:q+1]])
        elif (i > q) and (q > 0):
            score += sum([x[1] for x in blu[:q]])

        if score > A:
            max_k = k - 1
            break
        elif score == A:
            print(k)
            exit()
    else:
        min_k = k + 1
print(k)

Submission status: Wrong Answer

Solution code:
import sys
import math
sys.setrecursionlimit(10**7)

debug = True
debug = False

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

class Task:
    def __repr__(self):
        return str(self.__dict__)
    def time_toget_point(self, p):
        if p >= self.max_minus:
            return math.ceil(self.b + (p - self.max_minus)/self.u)
        else:
            return math.ceil(p/self.l)

def solve():
    n, x = map(int, input().split())
    t_list = []
    total_behind = 0 # これだけ点を取らなければならない

    for i in range(n):
        t = Task()
        t.b, t.l, t.u = map(int, input().split())

        t.max_minus = t.b * t.l # 重み最低で勉強しない場合のマイナス
        t.max_plus = (x-t.b) * t.u # 重み最高で満点まで勉強する時のプラス
        t.eff = t.max_plus + t.max_minus # 重み最高にした時の勉強効率
        t_list.append(t)

        total_behind += t.max_minus
    dprint(total_behind)

    # 重み最高での勉強効率の降順に並び変え
    t_list = sorted(t_list, key=lambda t: t.eff, reverse=True)
    dprint(t_list)

    total_time = 0 # 総勉強時間
    total_score = -1 * total_behind # マイナスからスタートし、0になったら勝ち
    for i, t in enumerate(t_list):
        # ためしに全力してみる
        total_score_tmp = total_score
        total_score_tmp += t.eff

        if total_score_tmp < 0:
            # まだ勉強が足りないので、このtaskをコミットして勉強を続ける
            total_score = total_score_tmp
            total_time += x
            dprint(i, total_score, total_time, "commited")
        else:
            # これを全力すると勉強しすぎの場合、いったん中止
            dprint(i, total_score, total_time, t.eff, "stop")
            break

    # 残り必要点数を稼ぐのにもっとも効率がいいものを探す
    dprint("ajusting", total_time, total_score)

    min_rest_time = -1 # 残りを稼ぐ最小勉強時間
    for t in t_list[i:]:
        rest_time = t.time_toget_point(-1*total_score)
        if min_rest_time == -1 or rest_time < min_rest_time:
            min_rest_time = rest_time

    print(int(total_time + min_rest_time))


solve()

Submission status: Wrong Answer

Solution code:
import sys
import math
sys.setrecursionlimit(10**7)

debug = True
debug = False

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

class Task:
    def __repr__(self):
        return str(self.__dict__)
    def time_toget_point(self, p):
        if p >= -1 * self.max_minus:
            return math.ceil(self.b + (p+self.max_minus)/self.u)
        else:
            return math.ceil(p/self.l)

def solve():
    n, x = map(int, input().split())
    t_list = []
    total_behind = 0 # これだけ点を取らなければならない

    for i in range(n):
        b, l, u = map(int, input().split())
        t = Task()
        t.b = b
        t.l = l
        t.u = u

        t.max_minus = -1 * b * l # 重み最低で勉強しない場合のマイナス
        t.max_plus = (x-b) * u # 重み最高で満点まで勉強する時のプラス
        t.eff = t.max_plus - t.max_minus # 重み最高にした時の勉強効率
        t_list.append(t)

        total_behind += t.max_minus

    t_list = sorted(t_list, key=lambda t: t.eff, reverse=True)
    dprint(t_list)

    total_time = 0
    total_score = total_behind # マイナスからスタートし、0になったら勝ち
    dprint(total_score)

    for i, t in enumerate(t_list):

        # ためしに全力してみる
        total_score_tmp = total_score
        if total_score < 0:
            total_score_tmp += t.eff

        if total_score_tmp < 0:
            # まだ勉強が足りないので、このtaskをコミットして勉強を続ける
            total_score = total_score_tmp
            total_time += x
            dprint(i, total_score, total_time, "commited")
        else:
            # これを全力すると勉強しすぎの場合、いったん中止
            dprint(i, total_score, total_time, t.eff, "stop")
            break

    # 残り必要点数を稼ぐのにもっとも効率がいいものを探す

    dprint("ajusting")
    dprint(total_time, total_score)

    min_rest_time = -1
    for t in t_list[i:]:
        rest_time = t.time_toget_point(-1*total_score)
        if min_rest_time == -1 or rest_time < min_rest_time:
            min_rest_time = rest_time


    print(int(total_time + min_rest_time))


solve()

Submission status: Wrong Answer

Solution code:
n, x = list(map(int, input().split()))
B = 0
blu = []
s = [0 for i in range(n)]

for i in range(n):
  b, l, u = list(map(int, input().split()))
  blu.append((b, l, u, x*u-b*u+b*l))
  B += b*l
blu.sort(key=lambda x: x[3], reverse=True)

for i in range(n):
  if i==0:
    s[i] = blu[i][3]
  else:
    s[i] = s[i-1] + blu[i][3]

ans = n*x
for i in range(n):
  ok = n*x
  ng = -1
  while ok-ng>1:
    A = 0
    mid = (ok+ng)//2
    k = mid//x
    t = mid%x
    if t==0:
      A += s[k-1]
    else:
      if i<k:
        A += s[k]
        A -= blu[i][3]
      else:
        A += s[k-1]
      if t<=blu[i][0]:
        A += t*blu[i][1]
      else:
        A += t*blu[i][2] - blu[i][0]*(blu[i][2]-blu[i][1])
    if A>=B:
      ok = mid
    else:
      ng = mid
  ans = min(ans, ok)

print(ans)

Submission status: Wrong Answer

Solution code:
def c():
    N, X = map(int, input().split())
    data, used = [], []
    ans = 0
    tkhs, aok = 0, 0
    for _ in range(N):
        b, l, u = map(int, input().split())
        aok += b * l
        v = b * l + (X - b) * u
        data.append([v, b, l, u])
    data.sort(reverse=True)
    for i, d in enumerate(data):
        v, b, l, u = d
        tkhs += X * u
        aok += b * (u - l)
        if tkhs >= aok:
            tkhs -= X * u
            aok -= b * (u - l)
            break
        used += [i]
    for _ in used:
        ans += X
        data.pop(0)
    diff = aok - tkhs
    tmp = 10 ** 16
    for d in data:
        v, b, l, u = d
        if diff <= b * l:
            tmp1 = (diff - 1) // l + 1
        else:
            tmp1 = (diff + b * (u - l) - 1) // u + 1
        tmp = min(tmp, tmp1)
    ans += tmp
    return ans
  

if __name__ == '__main__':
    ans = c()
    print(ans)

Submission status: Wrong Answer

Solution code:
def c():
    N, X = map(int, input().split())
    data, used = [], []
    ans = 0
    tkhs, aok = 0, 0
    for _ in range(N):
        b, l, u = map(int, input().split())
        aok += b * l
        v = (X - b) * u
        data.append([v, b, l, u])
    data.sort(reverse=True)
    for i, d in enumerate(data):
        v, b, l, u = d
        tkhs += X * u
        aok += b * (u - l)
        if tkhs >= aok:
            tkhs -= X * u
            aok -= b * (u - l)
            break
        used += [i]
    for _ in used:
        ans += X
        data.pop(0)
    diff = aok - tkhs
    tmp = 10 ** 16
    for d in data:
        v, b, l, u = d
        if diff <= b * l:
            tmp1 = ans + (diff - 1) // l + 1
        else:
            tmp1 = ans + (diff + b * (u - l) - 1) // u + 1
        tmp = min(tmp, tmp1)
    ans = tmp
    return ans


if __name__ == '__main__':
    ans = c()
    print(ans)

Submission status: Wrong Answer

Solution code:
def c():
    N, X = map(int, input().split())
    data, used = [], []
    ans = 0
    tkhs, aok = 0, 0
    for _ in range(N):
        b, l, u = map(int, input().split())
        aok += b * l
        v = (X - b) * u
        data.append([v, b, l, u])
    data.sort(reverse=True)
    for i, d in enumerate(data):
        v, b, l, u = d
        tkhs += X * u
        aok += b * (u - l)
        if tkhs >= aok:
            tkhs -= X * u
            aok -= b * (u - l)
            break
        used += [i]
    for _ in used:
        ans += X
        data.pop(0)
    diff = aok - tkhs
    tmp = 10 ** 16
    for d in data:
        v, b, l, u = d
        tmp1 = ans + -(-diff // l)
        tmp2 = ans + -(-(diff + b * (u - l)) // u)
        tmp = min(tmp, tmp1, tmp2)
    ans = tmp
    return ans


if __name__ == '__main__':
    ans = c()
    print(ans)

Submission status: Wrong Answer

Solution code:
n, x = list(map(int, input().split()))
B = 0
blu = []

for i in range(n):
  b, l, u = list(map(int, input().split()))
  blu.append((b, l, u, x*u-b*u+b*l))
  B += b*l
blu.sort(key=lambda x: x[3], reverse=True)

ok = n*x
ng = -1
while ok-ng>1:
  A = 0
  tB = B
  mid = (ok+ng)//2
  k = mid//x
  t = mid%x
  for i in range(k):
    tB += blu[i][0]*(blu[i][2]-blu[i][1])
    A += x*blu[i][2]
  if t!=0:
    if t<=blu[k][0]:
      A += t*blu[k][1]
    else:
      A += t*blu[k][2]
      tB += blu[k][0]*(blu[k][2]-blu[k][1])
  if A>=tB:
    ok = mid
  else:
    ng = mid

print(ok)

Submission status: Wrong Answer

Solution code:
n, x = list(map(int, input().split()))
B = 0
blu = []

for i in range(n):
  b, l, u = list(map(int, input().split()))
  blu.append((b, l, u, x*u-b*u+b*l))
  B += b*l
blu.sort(key=lambda x: x[3], reverse=True)

ok = n*x
ng = 0
while ok-ng>1:
  A = 0
  tB = B
  mid = (ok+ng)//2
  k = mid//x
  t = mid%x
  for i in range(k):
    tB += blu[i][0]*(blu[i][2]-blu[i][1])
    A += x*blu[i][2]
  if t!=0:
    if t<=blu[k][0]:
      A += t*blu[k][1]
    else:
      A += t*blu[k][2]
      tB += blu[k][0]*(blu[k][2]-blu[k][1])
  if A>=tB:
    ok = mid
  else:
    ng = mid

print(ok)

Submission status: Wrong Answer

Solution code:
def c():
    N, X = map(int, input().split())
    data = []
    ans = 0
    t = 0
    used = []
    for _ in range(N):
        b, l, u = map(int, input().split())
        t -= b * l
        v = (X - b) * u
        data.append([v, b, l, u])
    data.sort(reverse=True)
    for i, d in enumerate(data):
        v, b, l, u = d
        t += X * u - (b * (u - l))
        if t >= 0:
            t -= X * u - (b * (u - l))
            break
        used += [i]
    for _ in used:
        ans += X
        data.pop(0)
    tmp = 10 ** 9
    for d in data:
        v, b, l, u = d
        tmp1 = ans + -(-abs(t) // l)
        tmp = min(tmp, tmp1)
    ans = tmp
    return ans


if __name__ == '__main__':
    ans = c()
    print(ans)

Submission status: Wrong Answer

Solution code:
def c():
    # b l u (l<=c<=u) 1時間当たり有利さ(重み)を求めて高い順で処理していく
    N, X = map(int, input().split())
    data = []
    ans = 0
    t = 0
    used = []
    for _ in range(N):
        b, l, u = map(int, input().split())
        t -= b * l
        v = b * l + (X - b) * u
        data.append([v, b, l, u])
    data.sort(reverse=True)
    for i, d in enumerate(data):
        v, b, l, u = d
        ans += X
        t += X * u - (b * (u - l))
        if t >= 0:
            ans -= X
            t -= X * u - (b * (u - l))
            break
        used += [i]
    for _ in used:
        data.pop(0)
    tmp = 10 ** 9
    for d in data:
        v, b, l, u = d
        tmp1 = ans + -(-abs(t) // l)
        tmp2 = ans + -(-(abs(t) + (b * (u - l))) // u)
        tmp = min(tmp, tmp1, tmp2)
    ans = tmp
    return ans


if __name__ == '__main__':
    ans = c()
    print(ans)

Submission status: Wrong Answer

Solution code:
def c():
    N, X = map(int, input().split())
    data = []
    ans = 0
    t = 0
    used = []
    for _ in range(N):
        b, l, u = map(int, input().split())
        v = (X - b) * u
        data.append([v, b, l, u])
        t -= b * l
    data.sort(reverse=True)
    for i, d in enumerate(data):
        v, b, l, u = d
        ans += X
        t += X * u - (b * (u - l))
        if t >= 0:
            ans -= X
            t -= X * u - (b * (u - l))
            break
        used += [i]
    for _ in used:
        data.pop(0)
    tmp = 10 ** 9
    for d in data:
        v, b, l, u = d
        tmp1 = ans + -(-abs(t) // l)
        tmp2 = ans + -(-(abs(t) + (b * (u - l))) // u)
        tmp = min(tmp, tmp1, tmp2)
    ans = tmp
    return ans


if __name__ == '__main__':
    ans = c()
    print(ans)

Submission status: Wrong Answer

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

if pt==0:
    print(0)
    exit()

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

Submission status: Wrong Answer

Solution code:
n,x = map(int,input().split(' '))
b,l,u = [],[],[]
for i in range(n):
    t = input().split(" ")
    b.append(int(t[0]))
    l.append(int(t[1]))
    u.append(int(t[2]))

ans = 0
tkhs = 0
aoki = 0
max_dif = []
for i in range(n):
    max_dif.append((x - b[i]) * u[i])
    aoki += b[i] * l[i]

for i in range(n):
    if tkhs + x * u[max_dif.index(max(max_dif))] < aoki + b[max_dif.index(max(max_dif))] * (u[max_dif.index(max(max_dif))] - l[max_dif.index(max(max_dif))]):
        tkhs += x * u[max_dif.index(max(max_dif))]
        aoki += b[max_dif.index(max(max_dif))] * (u[max_dif.index(max(max_dif))] - l[max_dif.index(max(max_dif))])
        b.pop(max_dif.index(max(max_dif)))
        l.pop(max_dif.index(max(max_dif)))
        u.pop(max_dif.index(max(max_dif)))
        max_dif.pop(max_dif.index(max(max_dif)))
        ans += x
    elif tkhs + x * u[max_dif.index(max(max_dif))] >= aoki + b[max_dif.index(max(max_dif))] * (u[max_dif.index(max(max_dif))] - l[max_dif.index(max(max_dif))]) and tkhs < aoki:
        z = []
        for j in range(len(b)):
            z.append(((aoki + b[j] * (u[j] - l[j])) - tkhs)// u[j])
        ans += min(z)
        break
    else:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
n,x = map(int,input().split(' '))
b,l,u = [],[],[]
for i in range(n):
    t = input().split(" ")
    b.append(int(t[0]))
    l.append(int(t[1]))
    u.append(int(t[2]))

ans = 0
tkhs = 0
aoki = 0
max_dif = []
for i in range(n):
    max_dif.append((x - b[i]) * u[i])
    aoki += b[i] * l[i]

print(max_dif)

for i in range(n):
    if tkhs + x * u[max_dif.index(max(max_dif))] < aoki + b[max_dif.index(max(max_dif))] * (u[max_dif.index(max(max_dif))] - l[max_dif.index(max(max_dif))]):
        tkhs += x * u[max_dif.index(max(max_dif))]
        aoki += b[max_dif.index(max(max_dif))] * (u[max_dif.index(max(max_dif))] - l[max_dif.index(max(max_dif))])
        b.pop(max_dif.index(max(max_dif)))
        l.pop(max_dif.index(max(max_dif)))
        u.pop(max_dif.index(max(max_dif)))
        max_dif.pop(max_dif.index(max(max_dif)))
        ans += x
    elif tkhs + x * u[max_dif.index(max(max_dif))] >= aoki + b[max_dif.index(max(max_dif))] * (u[max_dif.index(max(max_dif))] - l[max_dif.index(max(max_dif))]) and tkhs < aoki:
        z = []
        for j in range(len(b)):
            z.append(((aoki + b[j] * (u[j] - l[j])) - tkhs)// u[j])
        ans += min(z)
        break
    else:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
n, x = list(map(int, input().split()))
B = 0
blu = []

for i in range(n):
  b, l, u = list(map(int, input().split()))
  blu.append((b, l, u, x*u-b*u+b*l))
  B += b*l
blu.sort(key=lambda x: x[3], reverse=True)

ok = n*x
ng = 0
while ok-ng>1:
  A = 0
  tB = B
  mid = (ok+ng)//2
  k = mid//x
  t = mid%x
  for i in range(k):
    tB += blu[i][0]*(blu[i][2]-blu[i][1])
    A += x*blu[i][2]
  if k<n:
    if t<=blu[k][0]:
      A += t*blu[k][1]
    else:
      A += t*blu[k][2]
      tB += blu[k][0]*(blu[k][2]-blu[k][1])
  if A>=tB:
    ok = mid
  else:
    ng = mid

print(ok)

Submission status: Wrong Answer

Solution code:
n, x = list(map(int, input().split()))
A = 0
B = 0
blu = []
cnt = 0
ans2 = 0

for i in range(n):
  b, l, u = list(map(int, input().split()))
  blu.append((b, l, u, x*u-b*u+b*l))
  B += b*l
blu.sort(key=lambda x: x[3], reverse=True)

ok = n*x
ng = 0
while ok-ng>1:
  A = 0
  tB = B
  mid = (ok+ng)//2
  k = mid//x
  t = mid%x
  for i in range(k):
    tB += blu[i][0]*(blu[i][2]-blu[i][1])
    A += x*blu[i][2]
  if t<=blu[k][0]:
    A += t*blu[k][1]
  else:
    A += t*blu[k][2]
    tB += blu[k][0]*(blu[k][2]-blu[k][1])
  if A >= tB:
    ok = mid
  else:
    ng = mid

print(ok)

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:
        break
ho=s[i:]
r=float("inf")
for j in ho:
    r=min(min((b+(j[2]-j[1])*j[0]-g-1)//j[2],(b-g-1)//j[1])+1,r)
print(e+r)