Problem:


Score : 800 points

Problem Statement

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

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

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

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

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

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

Constraints

1 \leq N \leq 10^5

1 \leq X \leq 10^5

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

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

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

2 100
85 2 3
60 1 1

Sample Output 1

115

One optimal strategy is as follows:

Choose c_1 = 3, c_2 = 1.

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

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

Sample Input 2

2 100
85 2 3
60 10 10

Sample Output 2

77

Sample Input 3

1 100000
31415 2718 2818

Sample Output 3

31415

Sample Input 4

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

Sample Output 4

2540



Sample input:
2 100
85 2 3
60 1 1


Sample output:
115

Submission status: Wrong Answer

Solution code:
import 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 = [(X*U[i] - B[i]*(U[i]-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 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 * (u - l) - 1) // u + 1, 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)

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)
    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
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:
            M=min(M0,M)
    else:
        M=min(M0,M)
print(ans+M)

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

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
L=sorted([list(map(int,input().split())) for _ in range(n)],key=lambda y:(x-y[0])*y[2])[::-1]
tk=0
for i in range(n):
    tk+=L[i][0]*L[i][1]
ans=0
p=0
for i in range(n):
    tk+=L[i][0]*(L[i][2]-L[i][1])
    ans+=x
    p+=x*L[i][2]
    if p>tk:
        while p>=tk:
            ans-=1
            p-=L[i][2]
        ans+=1
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)


def main():
    n,x = LI()
    aa = [LI() for _ in range(n)]
    t = 0
    a = []
    for b,l,u in aa:
        k = (x - b) * u + b * l
        t += l * b
        a.append((k,b,l,u))
    m = 10**6
    a.sort(key=lambda x: -x[0]*m+x[2])

    r = 0
    for k,b,l,u in a:
        if t == k:
            r += x
            break
        if t > k:
            t -= k
            r += x
            continue
        if t <= b*l:
            r += (t+l-1) // l
        else:
            r += b
            t -= b * l
            r += (t+u-1) // u
        break

    return r


print(main())

Submission status: Wrong Answer

Solution code:
print("わからない")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate

n, x = map(int, input().split())
BLU = [list(map(int, input().split())) for _ in range(n)]
B, L, U = zip(*BLU)
S = [b*l+(x-b)*u for b, l, u in BLU]
sortedS = sorted([(s, i) for i, s in enumerate(S)], reverse=True)
S, idx = zip(*sortedS)
B = [B[i] for i in idx]
L = [L[i] for i in idx]
U = [U[i] for i in idx]
M = sum([b*l for b, l, u in BLU])
A = list(accumulate(S))

def select(q, r):
  f = A[q]
  for i in range(n):
    temp = f - S[min(i, q)]
    temp += L[i]*min(B[i], r) + U[i]*max(r-B[i], 0)
    if temp>=M:
      return True
  return False

ng = -1
ok = sum(B)
while ok-ng > 1:
  mid = (ok+ng)//2
  q, r = divmod(mid, x)
  if select(q, r):
    ok = mid
  else:
    ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
read = sys.stdin.read
import numpy as np

n, x = map(int, input().split())
BLU = np.array(read().split(), dtype=np.int64).reshape(n, 3)
B, L, U = BLU.T
S = B*L + (x-B)*U
idx = np.argsort(S)[::-1]
S = S[idx]
B = B[idx]
L = L[idx]
U = U[idx]
M = (B*L).sum()

def select(q, r):
  f = sum(S[:q+1])
  for i in range(n):
    temp = f - S[min(i, q)]
    temp += L[i]*min(B[i], r) + U[i]*max(r-B[i], 0)
    if temp>=M:
      return True
  return False

ng = -1
ok = sum(B)
while ok-ng > 1:
  mid = (ok+ng)//2
  q, r = divmod(mid, x)
  if select(q, r):
    ok = mid
  else:
    ng = mid
print(ok)

Submission status: Time Limit Exceeded

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

def main():
  n, x = map(int, input().split())
  BLU = [list(map(int, input().split())) for _ in range(n)]
  B, L, U = zip(*BLU)
  S = [b*l+(x-b)*u for b, l, u in BLU]
  sortedS = sorted([(s, i) for i, s in enumerate(S)], reverse=True)
  S, idx = zip(*sortedS)
  B = [B[i] for i in idx]
  L = [L[i] for i in idx]
  U = [U[i] for i in idx]
  M = sum([b*l for b, l, u in BLU])

  def select(q, r):
    f = sum(S[:q+1])
    for i in range(n):
      temp = f - S[min(i, q)]
      temp += L[i]*min(B[i], r) + U[i]*max(r-B[i], 0)
      if temp>=M:
        return True
    return False

  ng = -1
  ok = sum(B)
  while ok-ng > 1:
    mid = (ok+ng)//2
    q, r = divmod(mid, x)
    if select(q, r):
      ok = mid
    else:
      ng = mid
  print(ok)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

n, x = map(int, input().split())
BLU = [list(map(int, input().split())) for _ in range(n)]
B, L, U = zip(*BLU)
S = [b*l+(x-b)*u for b, l, u in BLU]
sortedS = sorted([(s, i) for i, s in enumerate(S)], reverse=True)
S, idx = zip(*sortedS)
B = [B[i] for i in idx]
L = [L[i] for i in idx]
U = [U[i] for i in idx]
M = sum([b*l for b, l, u in BLU])

def select(q, r):
  f = sum(S[:q+1])
  for i in range(n):
    temp = f - S[min(i, q)]
    temp += L[i]*min(B[i], r) + U[i]*max(r-B[i], 0)
    if temp>=M:
      return True
  return False

ng = -1
ok = sum(B)
while ok-ng > 1:
  mid = (ok+ng)//2
  q, r = divmod(mid, x)
  if select(q, r):
    ok = mid
  else:
    ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
"""

重要度はlかuしかとらないと考えてよい
高橋君のほうが青木君より低い点数を取ると決めた科目に対してはl、それ以外はuと定める
それぞれのテストの点数の差をdとして、Σ[a>=b](d*u) - Σ[a<b](d*l) >= 0 を満たす
最小のΣaを求める
→各iについて、biまではli個ずつ減らすことができ、それより多く減らす場合はXを超えない範囲で
 ui個ずつ減らすことができる
→heapqでできそう
 単純なheapqだと、例えば一つのテストの中でlとuの値の差がとても大きい時に
 正しい答えが出せない
→二分探索

"""
import sys
input = sys.stdin.readline

n, x = map(int, input().split())
BLU = [list(map(int, input().split())) for _ in range(n)]
SBLU = sorted([(b*l+(x-b)*u, b, l, u) for b, l, u in BLU], reverse=True)
S, B, L, U = zip(*SBLU)
M = sum([b*l for b, l, u in BLU])

def select(q, r):
  f = sum(S[:q+1])
  for i in range(n):
    temp = f - S[min(i, q)]
    temp += L[i]*min(B[i], r) + U[i]*max(r-B[i], 0)
    if temp>=M:
      return True
  return False


ng = -1
ok = sum(B)
while ok-ng > 1:
  mid = (ok+ng)//2
  q, r = divmod(mid, x)
  if select(q, r):
    ok = mid
  else:
    ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
# 解説
def accumulate(a):
    su = 0
    yield su

    for x in a:
        su += x
        yield su


def solve_agc034c():
    from collections import namedtuple
    import sys
    input = sys.stdin.readline

    Test = namedtuple('Test', 'Aoki_score lower_bound upper_bound')
    Test.D_partial = lambda self, score: \
        self.lower_bound * score if score <= self.Aoki_score \
            else self.upper_bound * score - (self.upper_bound - self.lower_bound) * self.Aoki_score

    def is_ok(init_rest):
        """init_rest: 勉強に使える時間"""
        take, rest = divmod(init_rest, X)
        if take > N - 1:
            r = take - (N - 1)
            take = N - 1
            rest += r * X

        for i, partial_solve_test in enumerate(tests, start=1):
            when_full = partial_solve_test.D_partial(X)
            if i <= take:
                su = acc[take + 1] - when_full
            else:
                su = acc[take]

            when_partial = partial_solve_test.D_partial(min(X, rest))
            d = INIT_D + su + when_partial
            if d >= 0:
                return True

        return False

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

    N, X = map(int, input().split())
    tests = []
    for _ in range(N):
        row = map(int, input().split())
        tests.append(Test(*row))
    tests.sort(key=lambda test: test.D_partial(X), reverse=True)
    # 勝つ科目と負ける科目を決める
    # 勝つ科目は重要度をupper_boundにする
    # 負ける科目は重要度をlower_boundにする

    INIT_D = -sum(test.lower_bound * test.Aoki_score for test in tests)

    *acc, = accumulate(test.D_partial(X) for test in tests)

    res = binary_search(ok=10 ** 10, ng=-1, is_ok=is_ok)
    # D>=0となる勉強時間

    print(res)
    return


if __name__ == '__main__':
    solve_agc034c()

Submission status: Time Limit Exceeded

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

from itertools import accumulate

def main():
    N,X=map(int,input().split())
    A=[list(map(int,input().split())) for i in range(N)]

    A.sort(key=lambda x:x[2]*(X-x[0])+x[0]*x[1],reverse=True)
    ALL=[a[2]*(X-a[0])+a[0]*a[1] for a in A]



    SUM=[0]+list(accumulate(ALL))

    MAX=0
    MINUS=0

    for a,r,l in A:
        MAX+=a
        MINUS+=a*r

    OUT=-1

    def binsearch(score):

        alluse=score//X
        rest=score-alluse*X

        for ri in range(N):
            plus=0
            b,l,u=A[ri]
            
            if rest<b:
                plus+=rest*l
            else:
                plus+=rest*u+b*l-b*u

            if alluse<=ri:
                plus+=SUM[alluse]

            else:
                plus+=SUM[alluse+1]-ALL[ri]

            #print(score,ri,plus)

            if plus>=MINUS:
                return 1

        return 0


    while MAX-OUT>1:
        mid=(MAX+OUT)//2

        if binsearch(mid)==1:
            MAX=mid
        else:
            OUT=mid

    print(MAX)

main()

Submission status: Time Limit Exceeded

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

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

A.sort(key=lambda x:x[2]*(X-x[0])+x[0]*x[1],reverse=True)
ALL=[a[2]*(X-a[0])+a[0]*a[1] for a in A]

from itertools import accumulate

SUM=[0]+list(accumulate(ALL))

MAX=0
MINUS=0

for a,r,l in A:
    MAX+=a
    MINUS+=a*r

OUT=-1

def binsearch(score):

    alluse=score//X
    rest=score-alluse*X

    for ri in range(N):
        plus=0
        b,l,u=A[ri]
        
        if rest<b:
            plus+=rest*l
        else:
            plus+=rest*u+b*l-b*u

        if alluse<=ri:
            plus+=SUM[alluse]

        else:
            plus+=SUM[alluse+1]-ALL[ri]

        #print(score,ri,plus)

        if plus>=MINUS:
            return 1

    return 0


while MAX-OUT>1:
    mid=(MAX+OUT)//2

    if binsearch(mid)==1:
        MAX=mid
    else:
        OUT=mid

print(MAX)

Submission status: Time Limit Exceeded

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

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

A.sort(key=lambda x:x[2]*(X-x[0])+x[0]*x[1],reverse=True)
ALL=[a[2]*(X-a[0])+a[0]*a[1] for a in A]

from itertools import accumulate

SUM=[0]+list(accumulate(ALL))

MAX=0
MINUS=0

for a,r,l in A:
    MAX+=a
    MINUS+=a*r

OUT=-1

def binsearch(score):

    alluse=score//X
    rest=score-alluse*X

    for ri in range(N):
        plus=0
        
        if rest<A[ri][0]:
            plus+=rest*A[ri][1]
        else:
            plus+=rest*A[ri][2]+A[ri][0]*A[ri][1]-A[ri][0]*A[ri][2]

        if alluse<=ri:
            plus+=SUM[alluse]

        else:
            plus+=SUM[alluse+1]-ALL[ri]

        #print(score,ri,plus)

        if plus>=MINUS:
            return 1

    return 0


while MAX-OUT>1:
    mid=(MAX+OUT)//2

    x=binsearch(mid)

    if x==1:
        MAX=mid
    else:
        OUT=mid

print(MAX)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline

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

    accVs = list(accumulate([0] + vs, lambda accX, X: accX + X[0]))
    D0 = -sum([L*B for B, L, U in BLUs])

    def isOK(k):
        q = k // X
        r = k % X
        accV = accVs[q+1]
        for v, i in vs[:q]:
            B, L, U = BLUs[i]
            d = D0 + accV - v
            if r <= B:
                d += L*r
            else:
                d += L*B + U*(r-B)
            if d >= 0:
                return True
        accV = accVs[q]
        for v, i in vs[q:]:
            B, L, U = BLUs[i]
            d = D0 + accV
            if r <= B:
                d += L*r
            else:
                d += L*B + U*(r-B)
            if d >= 0:
                return True
        return False

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

    return ok


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

print(solve(N, X, BLUs))

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline

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

    accVs = list(accumulate([0] + vs, lambda accX, X: accX + X[0]))
    D0 = -sum([L*B for B, L, U in BLUs])

    def isOK(k):
        q = k // X
        r = k % X
        accV1, accV = accVs[q+1], accVs[q]
        for odr, (v, i) in enumerate(vs):
            B, L, U = BLUs[i]
            d = D0
            if odr < q:
                d += accV1 - v
            else:
                d += accV
            if r <= B:
                d += L*r
            else:
                d += L*B + U*(r-B)
            if d >= 0:
                return True
        return False

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

    return ok


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

print(solve(N, X, BLUs))

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

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

accVs = list(accumulate([0] + vs, lambda accX, X: accX + X[0]))
D0 = -sum([L*B for B, L, U in BLUs])

def isOK(k):
    q = k // X
    r = k % X
    for odr, (v, i) in enumerate(vs):
        B, L, U = BLUs[i]
        d = D0
        if odr < q:
            d += accVs[q+1] - v
        else:
            d += accVs[q]
        if r <= B:
            d += L*r
        else:
            d += L*B + U*(r-B)
        if d >= 0:
            return True
    return False

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

print(ok)

Submission status: Time Limit Exceeded

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)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

import numpy as np

if os.getenv('LOCAL'):
    sys.stdin = open('_in.txt', 'r')

sys.setrecursionlimit(2147483647)
INF = float('inf')


def bisect_right_callable(fn, x, lo, hi):
    """
    lo から hi-1 のうち、fn の結果が x 以下となる、最も右の値 + 1
    bisect.bisect_right と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= hi
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if x < fn(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


N, X = list(map(int, sys.stdin.readline().split()))
B, L, U = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

B = np.array(B, dtype=int)
L = np.array(L, dtype=int)
U = np.array(U, dtype=int)

# 全部 L で B 点とると仮定する
target = (B * L).sum()

# こうすれば target と比較できる
scores = B * L + (X - B) * U
scores_i = scores.argsort()

scores = scores[scores_i]
scores_cumsum = np.concatenate((scores[::-1].cumsum()[::-1], [0]))
B = B[scores_i]
L = L[scores_i]
U = U[scores_i]


def get_max_score(x):
    # x 点とったときの最大のスコア

    # 満点の数
    perfects = x // X
    # 途中まで頑張るやつは何点取ればいいか
    half_x = x % X

    max_score = 0
    for i in range(N):
        # i 番目のテストだけ途中まで頑張る
        # 満点の合計
        if i < N - perfects:
            score = scores_cumsum[N - perfects]
        else:
            score = scores_cumsum[N - perfects - 1] - scores[i]
        score += min(half_x, B[i]) * L[i] + (max(B[i], half_x) - B[i]) * U[i]
        max_score = max(max_score, score)
    return max_score


ans = bisect_right_callable(get_max_score, target - 1, 0, B.sum())
print(ans)

Submission status: Time Limit Exceeded

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

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


def f(num):
    cnt = num // X
    mod = num % X
    point = 0
    for i in range(cnt):
        point += items[i][3]
    for i in range(cnt, N):
        point += items[i][4]

    if mod == 0:
        if point >= 0:
            return True
        else:
            return False
    else:
        tmp = -float("inf")
        for i, tmp2 in enumerate(items):
            b, l, u, d1, d2 = tmp2
            if mod >= b:
                mul = u * (mod - b)
            else:
                mul = l * (mod - b)

            if i < cnt:
                tmp = max(tmp, point - d1 + mul + items[cnt][3] - items[cnt][4])
            else:
                tmp = max(tmp, point - d2 + mul)
        if tmp >= 0:
            return True
        else:
            return False

ok = N * X + 1
ng = - 1
while (ok - ng) > 1:
    mid = (ok + ng) // 2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

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

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


def f(num):
    cnt = num // X
    mod = num % X
    point = 0
    for i in range(cnt):
        point += items[i][3]
    for i in range(cnt, N):
        point += items[i][4]

    if mod == 0:
        if point >= 0:
            return True
        else:
            return False
    else:
        tmp = -float("inf")
        for i in range(N):
            b, l, u, d1, d2 = items[i]
            if mod >= b:
                mul = u * (mod - b)
            else:
                mul = l * (mod - b)

            if i < cnt:
                tmp = max(tmp, point - d1 + mul + items[cnt][3] - items[cnt][4])
            else:
                tmp = max(tmp, point - d2 + mul)
        if tmp >= 0:
            return True
        else:
            return False

ok = N * X + 1
ng = - 1
while (ok - ng) > 1:
    mid = (ok + ng) // 2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

n, m = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(n)]
t.sort(key=lambda x:(x[1]*x[0] + x[2]*(m-x[0])), reverse=True)
full = [x[1]*x[0] + x[2]*(m-x[0]) for x in t]
cum = [0]
for i in range(n):
	cum.append(cum[-1] + full[i])
aoki = sum([p[0]*p[1] for p in t])
ans = n*m
for i in range(n):
	ok, ng = n*m, -1
	while ok-ng > 1:
		x = (ok+ng) // 2
		res = cum[x//m]
		if (x//m)-1 >= i:
			res -= full[i]
			res += full[x//m]
		res += t[i][1] * min(t[i][0], x%m) + t[i][2] * max(0, (x%m) - t[i][0])
		if res >= aoki:
			ok = x
		else:
			ng = x
	ans = min(ans, ok)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(n)]
t.sort(key=lambda x:(x[1]*x[0] + x[2]*(m-x[0])), reverse=True)
full = [x[1]*x[0] + x[2]*(m-x[0]) for x in t]
cum = [0]
for i in range(n):
	cum.append(cum[-1] + full[i])
aoki = sum([p[0]*p[1] for p in t])
ans = n*m
for i in range(n):
	ok, ng = n*m, -1
	while ok-ng > 1:
		x = (ok+ng) // 2
		res = cum[x//m]
		if (x//m)-1 >= i:
			res -= full[i]
			res += full[x//m]
		res += t[i][1] * min(t[i][0], x%m) + t[i][2] * max(0, (x%m) - t[i][0])
		if res >= aoki:
			ok = x
		else:
			ng = x
	ans = min(ans, ok)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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
# print(q_array)
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
        # print(score_needed)
        for j in range(i, N):
            b, l, u, s = q_array[j]
            if score_needed > s:
                break
            yobun = s - score_needed
            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))
            for k in range(i):
                b, l, u, s = q_array[k]
                needed = s - yobun
                if score_needed <= b * l:
                    study_min = min(study_min, math.ceil(needed / l))
                else:
                    study_min = min(study_min, b + math.ceil(
                        (needed - b * l) / u))
        ans += study_min
        break
print(ans)

Submission status: Accepted

Solution code:

"""

https://atcoder.jp/contests/agc034/tasks/agc034_c

cをどうやって決めるか考える
差分で考えることとする
負けることにする場合、cが大きいほど負けがかさむので l
そうでない場合、重要度を uにするべき

勝ちを増やす or 負けを減らすの、どっちの方が良い…？

bが小さいほうを勝ち、大きいほうを負けにした方がいい説
bが小さいほうで負け、大きいほうで勝つ場合を考えてみる
a1 < b1 < b2 < a2 とする。
この時、寄与は (a2-b2)*u2-(b1-a1)*l1 = X
aの値を交換してみると、寄与は
(a2-b1)*u1 - (b2-a1) * l2 = Y
となる。
Y-X = 
となり改善するので示された

bが小さいほうからi個を勝ちにする場合の最小を考えればいい
→あとは全探索すれば終わり

うわー luは固定じゃないんかい
とりあえず勝ち負けを決めた場合のスコア計算を考えてみる
最初全部負けで考え、損失の和Pを計算しておく→Σbi*li
N個のコインタワーがあり、上からbi個の価値はli、残りはuiである
Pを超える価値を取るための最小の枚数を求めよ
上を取っておいて下を取らない意味がないので、取ると決めたら山全部取るのが最適
→山の総和が大きい順にソート
→最大の山を全部取っても足りない場合、取りつくす
→最後の1山は残りから全探索する

なぜWA?
分からん…
山を上からとらない理由がない

4,4,93 →和101
2,2,96 →和100
104
→大きいほうからとっていいなんてことはなかった
→総和が大きい山を必ずすべて使うという未証明命題を使おうとしたのが敗因

"""

from sys import stdin

N,X = map(int,stdin.readline().split())

P = 0
sblu = [] #山の総和s,b,l,u

for i in range(N):
    b,l,u = map(int,stdin.readline().split())
    s = b * l + (X-b) * u
    P += b * l
    sblu.append((s,b,l,u))

sblu.sort()
sblu.reverse()

ans = float("inf")
slis = []
for i in range(N):
    if i == 0:
        slis.append(sblu[i][0])
    else:
        slis.append(slis[-1] + sblu[i][0])

for i in range(N): #iは中途半端に取る場所

    #iも含めた和がPを超える最小のindexを求める
    L = -1
    R = N-1
    while R-L != 1:
        
        M = (R+L)//2
        if M < i:
            if slis[M] + sblu[i][0] >= P:
                R = M
            else:
                L = M
        else:
            if slis[M] >= P:
                R = M
            else:
                L = M

    if R < i:
        rem = P - slis[R]
        nans = X * (R+1)
    else:
        rem = P - (slis[R]-sblu[i][0])
        nans = X * R

    if rem < 0 or sblu[i][0] < rem:
        continue

    s,b,l,u = sblu[i]
    if rem <= b*l:
        nans += (rem+l-1) // l
    else:
        rem = rem - b * l
        nans += b + (rem+u-1)//u

    ans = min(ans,nans)

print (ans)

Submission status: Accepted

Solution code:
N,X=map(int,input().split())
t=[]
s=0
for i in range(N):
    b,l,u=map(int,input().split())
    t.append(((X-b)*u+l*b,b,l,u))
    s-=b*l
t.sort()
def condition(q):
    check=sum(t[i][0] for i in range(N-q,N))
    return check+s>=0

start=0
end=N
while end-start>1:
    test=(end+start)//2
    if not condition(test):
        start=test
    else:
        end=test

if not condition(end):
    Q=end
else:
    Q=start

check=sum(t[i][0] for i in range(N-Q,N))
check2=check+t[N-Q-1][0]
def condition2(r):
    M=0
    for i in range(N):
        test=0
        if N-Q>i:
            test=check
            val,b,l,u=t[i]
            if b>=r:
                test+=r*l
            else:
                test+=r*u-b*(u-l)
            M=max(M,test)
        else:
            val,b,l,u=t[i]
            test=check2-val
            if b>=r:
                test+=r*l
            else:
                test+=r*u-b*(u-l)
            M=max(M,test)
    return M+s>=0

start=0
end=X-1
while end-start>1:
    mid=(end+start)//2
    if condition2(mid):
        end=mid
    else:
        start=mid

if condition2(start):
    R=start
elif condition2(end):
    R=end
else:
    R=X
print(Q*X+R)

Submission status: Accepted

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

S=0
data=[]

low=0
high=0

for i in range(N):
    b,l,u=blu[i]
    high+=b
    data.append([u*(X-b)+l*b,i])
    S-=b*l
data.sort(reverse=True)

lst=[data[0][0]]
lsls=[data[0][1]]
for i in range(1,N):
    lst.append(lst[-1]+data[i][0])
    lsls.append(data[i][1])

while high-low>1:
  
    mid=(high+low)//2
    ppp=mid//X
    qqq=mid%X
    
    SS=S
    if ppp>0:
        SS+=lst[ppp-1]
    num=0
    for i in range(ppp,N):
        b,l,u=blu[lsls[i]]
        if qqq>=b:
            num1=b*l+(qqq-b)*u
        else:
            num1=qqq*l
        num=max(num,num1)
    SS+=num
    
    SSS=S+lst[ppp]
    num=-float("inf")
    for i in range(ppp):
        zzz,ind=data[i]
        b,l,u=blu[ind]
        if qqq>=b:
            num1=-zzz+b*l+(qqq-b)*u
        else:
            num1=-zzz+qqq*l
        num=max(num,num1)
    SSS+=num
    
    SS=max(SS,SSS)
    if SS>=0:
        high=mid
    else:
        low=mid

print(high)