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 heapq import heappush, heappop
import re
from collections import deque
import sys
input = sys.stdin.readline


def int_raw():
    return int(input())


def ss_raw():
    return input().split()


def ints_raw():
    return tuple(map(int, ss_raw()))


DIV = 10**9+7


def mod_invs(n, mod=DIV):
    inv = [0]*(n+1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, n+1):
        inv[i] = (-(mod//i)*inv[mod % i]) % mod
    return inv


N, X = ints_raw()

#N = int_raw()


def main():
    blus = [ints_raw() for _ in range(N)]
    aps = [blu[0]*blu[1] for blu in blus]
    atdp = sum(aps)
    #blus = [[(X-blu[0])*blu[2]+blu[0]*blu[1]]+list(blu) for blu in blus]
    blus = [[(X-blu[0])*blu[2]+blu[0]*blu[1]]+list(blu) for blu in blus]

    blus.sort(reverse=True)

    lowest = []
    for idx in range(N):
        blu = blus[idx]
        heappush(lowest, [-blu[2], idx])
    ans_t = 0
    idx = 0
    for blu in blus:
        d, b, l, u = blu
        if atdp <= 0:
            return ans_t

        lblu = blus[lowest[0][1]]
        if lblu[2]*lblu[1] >= atdp:
            return ans_t + ((atdp+lblu[2]-1)//lblu[2])

        atdp += b*(u-l)
        if X*u >= atdp:
            return ans_t + ((atdp+u-1)//u)
        else:
            atdp -= X*u
            ans_t += X
        if idx == lowest[0][1]:
            heappop(lowest)
        idx += 1
    return ans_t


print(main())

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
import re
from collections import deque
import sys
input = sys.stdin.readline


def int_raw():
    return int(input())


def ss_raw():
    return input().split()


def ints_raw():
    return tuple(map(int, ss_raw()))


DIV = 10**9+7


def mod_invs(n, mod=DIV):
    inv = [0]*(n+1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, n+1):
        inv[i] = (-(mod//i)*inv[mod % i]) % mod
    return inv


N,X= ints_raw()

#N = int_raw()


def main():
    blus = [ints_raw() for _ in range(N)]
    aps = [blu[0]*blu[1] for blu in blus]
    atdp = sum(aps)
    #blus = [[(X-blu[0])*blu[2]+blu[0]*blu[1]]+list(blu) for blu in blus]
    blus = [[(X-blu[0])*blu[2]+blu[0]*blu[1]]+list(blu) for blu in blus]

    blus.sort(reverse=True)
    
    lowest =[]
    for idx in range(N):
        blu = blus[idx]
        heappush(lowest,[-blu[2],idx])
    ans_t = 0
    idx = 0
    for blu in blus:
        d,b,l,u = blu
        if atdp<=0:
            return ans_t

        lblu = blus[lowest[0][1]]
        cand1 = DIV
        if lblu[2]*lblu[1] >= atdp:
            cand1 =  ans_t + ((atdp+lblu[2]-1)//lblu[2])
            
        atdp += b*(u-l)
        if X*u >= atdp:
            return min(cand1,ans_t + ((atdp+u-1)//u))
        
        else:
            atdp -= X*u
            ans_t +=X
            if ans_t >= cand1:
                return cand1
        if idx == lowest[0][1]:
            heappop(lowest)
        idx+=1
    return ans_t
print(main())

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

score = 0
e = []
for idx in range(N):
    b, l, u = map(int, input().split())
    score -= b * l
    adv = (X - b) * u + b * l
    e.append((b, l, u, adv))

e.sort(key=itemgetter(3), reverse=True)  # adv降順ソート
c_adv = [0]
for b, l, u, adv in e:
    c_adv.append(c_adv[-1] + adv)


def is_ok(total):
    x_subject_count, remain_score = divmod(total, X)
    if remain_score > 0:
        for remain_subject_index in range(N):
            b, l, u, adv = e[remain_subject_index]
            remain_adv = (remain_score - b) * (u if b <= remain_score else l) + b * l

            if remain_subject_index >= x_subject_count:
                if remain_adv + c_adv[x_subject_count] + score >= 0:
                    return True
            else:
                if remain_adv + c_adv[x_subject_count + 1] - adv + score >= 0:
                    return True
    return False


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


print(binary_search())

Submission status: Wrong Answer

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

vs = [(U*(X-B)+L*B, i) for i, (B, L, U) in enumerate(BLUs)]
vs.sort(reverse=True)

ans = 0
diff = sum([L*B for B, L, U in BLUs])
useds = [False] * N
for v, i in vs:
    if diff-v < 0:
        minC = X
        for j in range(N):
            if useds[j]: continue
            B, L, U = BLUs[j]
            if diff <= L*B:
                c = -(-diff // L)
            else:
                c = B + -(-(diff-L*B) // U)
            minC = min(minC, c)
        ans += minC
        break
    ans += X
    diff -= v
    useds[i] = True

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

b = np.empty(N, dtype=int)
l = np.empty(N, dtype=int)
u = np.empty(N, dtype=int)

for n in range(N):
    b[n], l[n], u[n] = map(int, input().split())

c = X * u - b*(u - l)
di = np.argsort(c)[::-1]
c = c[di]
b = b[di]
l = l[di]
u = u[di]
bl = b * l
bsum = bl.sum()

# 累乗和
c_cumsum = np.cumsum(c)
c_p = np.searchsorted(c_cumsum, bsum, side='left')

if bsum == c_cumsum[c_p]:
    print((c_p + 1)*X)
    exit(0)

if c_p > 0:
    left = bsum - c_cumsum[c_p - 1]
else:
    left = bsum

#ans = np.empty(N, dtype=int)
# left1 = left - c[c_p]
# ans[:c_p] = np.where(left1 + c[:c_p] <= bl[:c_p], (left1 + c[:c_p] - 1) // l[:c_p] + 1, (left1 + c[:c_p] - bl[:c_p] - 1) // u[:c_p] + b[:c_p] + 1)
ans = np.where(left <= bl[c_p:], (left - 1) // l[c_p:] + 1, (left - bl[c_p:] - 1) // u[c_p:] + b[c_p:] + 1)
print(c_p * X + ans.min())

Submission status: Wrong Answer

Solution code:
import numpy as np

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

b = np.empty(N, dtype=int)
l = np.empty(N, dtype=int)
u = np.empty(N, dtype=int)

for n in range(N):
    b[n], l[n], u[n] = map(int, input().split())

c = X * u - b*(u - l)
di = np.argsort(c)[::-1]
c = c[di]
b = b[di]
l = l[di]
u = u[di]
bl = b * l
bsum = bl.sum()

# 累乗和
c_cumsum = np.cumsum(c)
#
c_p = np.searchsorted(c_cumsum, bsum, side='left')

if bsum == c_cumsum[c_p]:
    print((c_p + 1)*X)
    exit(0)

if c_p > 0:
    left = bsum - c_cumsum[c_p - 1]
else:
    left = bsum

ans = np.empty(N, dtype=int)
left1 = left - c[c_p]
ans[:c_p] = np.where(left1 + c[:c_p] <= u[:c_p] * l[:c_p], (left1 + c[:c_p] - 1) // l[:c_p] + 1, (left1 + c[:c_p] + b[:c_p] * (u[:c_p] - l[:c_p]) - 1) // u[:c_p] + 1)
ans[c_p:] = np.where(left <= u[c_p:] * l[c_p:], (left - 1) // l[c_p:] + 1, (left + b[c_p:] * (u[c_p:] - l[c_p:]) - 1) // u[c_p:] + 1)
ans = c_p * X + ans.min()
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

remain_norma = norma
sub_d = -1
i = 0
used = set()
for i, (d, b, l, u, ei) in enumerate(exams_sorted):
    if remain_norma < d:
        sub_d = d
        break
    remain_norma -= d
    used.add(ei)

base_ans = i * x
base_remain_norma = remain_norma

if remain_norma == 0:
    print(base_ans)
    exit()

ans = 10 ** 10

for d, b, l, u, i in exams:
    if i in used:
        curr_remain_norma = base_remain_norma + d - sub_d
    else:
        curr_remain_norma = base_remain_norma
    if curr_remain_norma <= b * l:
        extra = (curr_remain_norma - 1) // l + 1
    else:
        extra = (curr_remain_norma + b * (u - l) - 1) // u + 1
    if extra > x:
        continue
    ans = min(ans, base_ans + extra)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

remain_norma = norma
sub_d = -1
base_ans = 0
used = set()
for i, (d, b, l, u, ei) in enumerate(exams_sorted):
    if remain_norma < d:
        sub_d = d
        base_ans = i * x
        break
    remain_norma -= d
    used.add(ei)

if remain_norma == 0:
    print(base_ans)
    exit()

base_remain_norma = remain_norma

ans = 10 ** 10

for d, b, l, u, i in exams:
    if i in used:
        curr_remain_norma = base_remain_norma + d - sub_d
    else:
        curr_remain_norma = base_remain_norma
    if curr_remain_norma <= b * l:
        extra = (curr_remain_norma - 1) // l + 1
    else:
        extra = (curr_remain_norma + b * (u - l) - 1) // u + 1
    if extra > x:
        continue
    ans = min(ans, base_ans + extra)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

remain_norma = norma
sub_d = -1
base_ans = 0
used = set()
for i, (d, b, l, u, ei) in enumerate(exams_sorted):
    if remain_norma < d:
        sub_d = d
        base_ans = i * x
        break
    remain_norma -= d
    used.add(ei)

base_remain_norma = remain_norma

ans = 10 ** 10

for d, b, l, u, i in exams:
    if i in used:
        curr_remain_norma = base_remain_norma + d - sub_d
    else:
        curr_remain_norma = base_remain_norma
    if curr_remain_norma <= b * l:
        extra = (curr_remain_norma - 1) // l + 1
    else:
        extra = (curr_remain_norma + b * (u - l) - 1) // u + 1
    if extra > x:
        continue
    ans = min(ans, base_ans + extra)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

remain_norma = norma
i = 0
used = set()
for i, (d, b, l, u, ei) in enumerate(exams_sorted):
    if remain_norma < d:
        break
    remain_norma -= d
    used.add(ei)

ans = 10 ** 10
sub_i = i
sub_d = exams[i][0]
base_ans = i * x
base_remain_norma = remain_norma

for d, b, l, u, i in exams:
    if i in used:
        curr_remain_norma = base_remain_norma + d - sub_d
    else:
        curr_remain_norma = base_remain_norma
    if curr_remain_norma <= b * l:
        extra = (curr_remain_norma - 1) // l + 1
    else:
        extra = (curr_remain_norma + b * (u - l) - 1) // u + 1
    if extra > x:
        continue
    ans = min(ans, base_ans + extra)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

b = np.empty(N, dtype=int)
l = np.empty(N, dtype=int)
u = np.empty(N, dtype=int)

for n in range(N):
    b[n], l[n], u[n] = map(int, input().split())

bl = b * l
bsum = bl.sum()
c = X * u - b*(u - l)

di = np.argsort(c)
c.sort()
d = c[::-1]
dc = np.cumsum(d)
dp = np.searchsorted(dc, bsum, side='left')

if bsum == dc[dp]:
    print((dp + 1)*X)
    exit(0)

if dp == 0:
    z = 0
    left = bsum
else:
    z = dp
    while z > 0 and d[z - 1] == d[dp]:
        z -= 1
    left = bsum - dc[dp - 1]

c1 = np.minimum((left - 1) // l + 1, (left + b * (u - l) - 1) // u + 1)
ans = dp * X + c1[di[:N - z]].min()
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

b = np.empty(N, dtype=int)
l = np.empty(N, dtype=int)
u = np.empty(N, dtype=int)

for n in range(N):
    b[n], l[n], u[n] = map(int, input().split())

bl = b * l
bsum = bl.sum()
c = X * u - b*(u - l)

di = np.argsort(c)
c.sort()
d = c[::-1]
dc = np.cumsum(d)
dp = np.searchsorted(dc, bsum, side='left')

if bsum == dc[dp]:
    print((dp + 1)*X)
    exit(0)

if dp == 0:
    z = 0
    left = bsum
else:
    z = dp
    while z > 0 and d[z - 1] == d[dp]:
        z -= 1
    left = bsum - dc[dp - 1]

c1 = np.where(left <= bl, (left - 1) // l + 1, (left + b * (u - l) - 1) // u + 1)
ans = dp*X + c1[di[:N - z]].min()
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
from itertools import accumulate
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)
    mXacc = list(accumulate([f(i, X) for _, i in mh]))
    m0acc = list(accumulate([f(i, 0) for _, i in mh]))
    # print(mh)
    # print(mX)
    # print(mXacc)
    # print(m0)
    # print(m0acc)

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

    def binary_search(key):
        ng = -1
        ok = N*X
        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            # print("ng, mid, ok = {}, {}, {}".format(ng, mid, ok))
            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: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
from itertools import accumulate
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)
    mX = [f(i, X) for _, i in mh]
    mXacc = list(accumulate(mX))
    m0 = [f(i, 0) for _, i in mh]
    m0acc = list(accumulate(m0))
    # print(mh)
    # print(mX)
    # print(mXacc)
    # print(m0)
    # print(m0acc)

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

    def binary_search(key):
        ng = -1
        ok = N*X
        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            # print("ng, mid, ok = {}, {}, {}".format(ng, mid, ok))
            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: Wrong Answer

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

s_score_list = []
full_score_list = []
for i, (b, l, u) in enumerate(blu):
    s_score_list.append(b * l)
    full_score_list.append([(x-b) * u + b * l, i])
s_score = sum(s_score_list)
full_score_list.sort(reverse=True)

t_score = 0
full_score_set = set()
for i in range(n):
    full_score_set.add(i)
    t_score += full_score_list[i][0]
    if t_score >= s_score:
        last_index = i
        surplus = t_score - s_score
        shortage = s_score - t_score + full_score_list[last_index][0]
        break

# Minimize time in full-score-set
max_reduction = 0
for i, (b, l, u) in enumerate(blu):
    if i in full_score_set:
        if (x-b) * u >= surplus:
            max_reduction = max(max_reduction, int(math.floor(surplus / u)))
        elif (x-b) * u + b * l >= surplus:
            max_reduction = max(max_reduction, (x-b) + int(math.floor((surplus - (x-b)*u) / l)))
ans = x * len(full_score_set) - max_reduction

# Take lest of score in not full_scores
full_score_set.remove(last_index)
min_promotion = INF
for i, (b, l, u) in enumerate(blu):
    if i in full_score_set:
        continue
    if b*l >= shortage:
        min_promotion = min(min_promotion, int(math.floor(shortage / l)))
    elif b*l + (x-b)*u >= shortage:
        min_promotion = min(min_promotion, b + int(math.floor((shortage - b*l) / u)))
ans = min(ans, min_promotion + x * len(full_score_set))
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

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

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 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: Wrong Answer

Solution code:
n, X = map(int, input().split())
test = [list(map(int, input().split())) for _ in range(n)]
test = sorted(test, key=lambda x: x[1] * x[0] + x[2] * (X - x[0]))
D = sum( x[0] * x[1]for x in test)
count = 0
for i in range(n):
    d, l, u = test[-1]
    sum = l * d + u *(X - d)
    if D - sum > 0:
        count += X
        D -= sum
        test.pop()
        continue
    break
list = []
for j in range(len(test)):
    tem_count = count
    tem_D = D
    d, l, u = test[j]
    for i in range(X):
        if i + 1 <= d:
            tem_D -= l
        else:
            tem_D -= u
        tem_count += 1
        if tem_D <= 0:
            list.append(tem_count)
            break
print(min(list))

Submission status: Wrong Answer

Solution code:
n, X = map(int, input().split())
test = [list(map(int, input().split())) for _ in range(n)]
test = sorted(test, key=lambda x: x[1] * x[0] + x[2] * (X - x[0]))
D = sum( x[0] * x[1]for x in test)
ans = 0
for i in range(n):
    d, l, u = test[-1]
    sum = l * d + u *(X - d)
    if D - sum > 0:
        ans += X
        D -= sum
        test.pop()
        continue
    break

test = sorted(test, key=lambda x: x[2])
d, l, u = test[-1]
for i in range(X):
    if i + 1 <= d:
        D -= l
    else:
        D -= u
    ans += 1
    if D <= 0:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
n, X = map(int, input().split())
test = [list(map(int, input().split())) for _ in range(n)]
test = sorted(test, key=lambda x: x[1] * x[0] + x[2] * (X - x[0]))
D = sum( x[0] * x[1]for x in test)
ans = 0
for i in range(n):
    d, l, u = test[-1]
    sum = l * d + u *(X - d)
    if D - sum > 0:
        ans += X
        D -= sum
        test.pop()
        continue
    break
d, l, u = test[-1]
for i in range(X):
    if i + 1 <= d:
        D -= l
    else:
        D -= u
    ans += 1
    if D <= 0:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,x=map(int,input().split())
BLU=[list(map(int,input().split())) for _ in range(n)]
for i in range(n):
    b,l,u=BLU[i]
    BLU[i].append(l*b+u*(x-b))
BLU.sort(key=lambda x: -x[3])
acc=0
Acc=[0]*(n+1)
for i in range(n):
    acc+=BLU[i][3]
    Acc[i+1]=acc
s=sum(-BLU[i][1]*BLU[i][0] for i in range(n))

def judge(k):
    q=k//x; r=k%x
    t=0
    if r==0:
        if Acc[q]+s>=0:
            return True
        return False
    for i in range(n):
        t=score(i,q,r)
        if t+s>=0:
            return True
    return False

def score(a,q,r):
    b,l,u,f=BLU[a]
    if r<=b:
        t=l*r
    else:
        t=l*b+u*(r-b)
    if a<=q-1:
        t+=Acc[q+1]-f
    else:
        t+=Acc[q]
    return t

l=0; r=n*x
while l+1<r:
    k=(l+r)//2
    if judge(k):
        r=k
    else:
        l=k
print(r)

Submission status: Wrong Answer

Solution code:
import math
n,x=(int(i) for i in input().split())
a=[]
r=0 #点差
l=0 #勉強時間
for i in range(n):
  c,d,e=(int(i) for i in input().split())
  r=r+c*d
  a.append([e,c,d])#eでソートしたいのでこの順番
  a.sort()
for i in range(n):
  k=(a[-1-i][0])*(x-a[-1-i][1]) #稼げる最大のアド
  if r-a[-1-i][1]*a[-1-i][2]>=k:
    l=l+x
    r=r-(a[-1-i][1]*a[-1-i][2])-k
  elif r>=a[-1-i][1]*a[-1-i][2]:
    l=l+a[-1-i][1]+(r-a[-1-i][1]*a[-1-i][2])/(a[-1-i][0])
    break
  elif r<a[-1-i][1]*a[-1-i][2]:
    l=l+r/(a[-1-i][2])
    break
print(math.floor(l))

Submission status: Wrong Answer

Solution code:
import math
n,x=(int(i) for i in input().split())
a=[]
r=0 #点差
l=0 #勉強時間
for i in range(n):
  c,d,e=(int(i) for i in input().split())
  r=r+c*d
  a.append([e,c,d])#eでソートしたいのでこの順番
  a.sort()
for i in range(n):
  k=(a[-1-i][0])*(x-a[-1-i][1]) #稼げる最大のアド
  if r-a[-1-i][1]*a[-1-i][2]>=k:
    l=l+x
    r=r-(a[-1-i][1]*a[-1-i][2])-k
  elif r>=a[-1-i][1]*a[-1-i][2]:
    l=l+a[-1-i][1]+(r-a[-1-i][1]*a[-1-i][2])/(a[-1-i][0])
    break
  elif r<a[-1-i][1]*a[-1-i][2]:
    l=l+r//(a[-1-i][2])
    break
print(math.floor(l))

Submission status: Wrong Answer

Solution code:
n,x=(int(i) for i in input().split())
a=[]
r=0 #点差
l=0 #勉強時間
for i in range(n):
  c,d,e=(int(i) for i in input().split())
  r=r+c*d
  a.append([e,c,d])#eでソートしたいのでこの順番
  a.sort()
for i in range(n):
  k=(a[-1-i][0])*(x-a[-1-i][1]) #稼げる最大のアド
  if r-a[-1-i][1]*a[-1-i][2]>=k:
    l=l+x
    r=r-(a[-1-i][1]*a[-1-i][2])-k
  elif r>=a[-1-i][1]*a[-1-i][2]:
    l=l+a[-1-i][1]+(r-a[-1-i][1]*a[-1-i][2])//(a[-1-i][0])
    break
  elif r<a[-1-i][1]*a[-1-i][2]:
    l=l+r//(a[-1-i][2])
    break
print(l)

Submission status: Wrong Answer

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

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

q_array = []
s_array = []

score_needed = 0

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

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

print(ans_max)

Submission status: Wrong Answer

Solution code:
n,x=(int(i) for i in input().split())
a=[]
r=0 #始めの点差
l=0 #勉強時間
for i in range(n):
  c,d,e=(int(i) for i in input().split())
  r=r+c*d
  a.append([e,c,d]) #eでソートしたいのでこの順番
for i in range(n):
  k=(a[-1-i][0])*(x-a[-1-i][1]) #稼げる最大のアド
  if r-a[-1-i][1]*a[-1-i][2]>=k:
    l=l+x
    r=r-a[-1-i][1]*a[-1-i][2]-k
  elif r>=a[-1-i][1]*a[-1-i][2]:
    l=l+a[-1-i][1]+(r-a[-1-i][1]*a[-1-i][2])//(a[-1-i][0])
    break
  elif r<a[-1-i][1]*a[-1-i][2]:
    l=l+r//(a[-1-i][2])
    break
print(l)

Submission status: Wrong Answer

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

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

sum = 0
while len(blu)>0:
    v,b,l,u = blu.pop()
    nxtpt = pt + l*b + u*(x-b)
    ddprint("v {} b {} l {} u {} pt {} nx {} sum {}".format(v,b,l,u,pt,nxtpt,sum))
    if nxtpt < 0:
        pt = nxtpt
        sum += x
        continue
    elif nxtpt == 0:
        pt = 0
        sum += x
        print(sum)
        exit()
    else:  # nxtpt > 0
        blu.append((v,b,l,u))
        break

# on the next step, we can go above zero
mn = 19999999999
for z in blu:
    v,b,l,u = z
    m = pt + l*b
    ddprint("m {}".format(m))
    if m>=0:
        t = b - (m)//l
    else:
        m = -m
        t = b + (m+u-1)//u
        if t>x:
            continue
    if t<mn:
        mn = t

print(sum+mn)

Submission status: Wrong Answer

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

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

sum = 0
while len(blu)>0:
    v,b,l,u = blu.pop()
    nxtpt = pt + l*b + u*(x-b)
    ddprint("v {} b {} l {} u {} pt {} nx {} sum {}".format(v,b,l,u,pt,nxtpt,sum))
    if nxtpt < 0:
        pt = nxtpt
        sum += x
        continue
    elif nxtpt == 0:
        pt = 0
        sum += x
        print(sum)
        exit()
    else:  # nxtpt > 0
        blu.append((v,b,l,u))
        break

# on the next step, we can go above zero
mn = 999999999
for z in blu:
    v,b,l,u = z
    m = pt + l*b
    ddprint("m {}".format(m))
    if m>=0:
        t = b - (m)//l
    else:
        m = -m
        t = b + (m+u-1)//u
        if t>x:
            continue
    if t<mn:
        mn = t

print(sum+mn)