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:

"""

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山は残りから全探索する

"""

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

ans = 0
while len(sblu) > 0 and P >= sblu[-1][0]:
    P -= sblu[-1][0]
    ans += X
    del sblu[-1]

#print (P,sblu)

if P > 0:
    ansplus = float("inf")
    for s,b,l,u in sblu:
        np = 0
        if b * l >= P:
            np = (P+l-1)//l
        else:
            tmpP = P - b * l
            np = (tmpP+u-1)//u + b
        
        ansplus = min(ansplus , np)
else:
    ansplus = 0

print (ans + ansplus)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
n,x = map(int,input().split())
blr = [list(map(int,input().split())) for i in range(n)]
tad = [[(x-b)*r+b*l,(x-b)*r,b*l,i] for i,(b,l,r) in enumerate(blr)]
tad.sort(key = lambda x:x[1],reverse=True)
tacc = list(accumulate(list(zip(*tad))[1]))
aacc = list(accumulate(list(zip(*tad))[2]))
p = -10**18
ans = 0
cand = []
for i in range(n):
  if tacc[i] >= aacc[n-1]-aacc[i] and p < 0:
    p = i
    ans += i*x
    if p == 0:
      ttot = 0
      atot = aacc[n-1]
    else:
      ttot = tacc[p-1]
      atot = aacc[n-1]-aacc[p-1]
    dif = atot-ttot
  if p >= 0:
    idx = tad[i][3]
    b,l,r = blr[idx]
    if dif <= tad[i][2]:
      cand.append((dif+l-1)//l)
    else:
      cand.append(b+(dif-b*l+r-1)//r)
print(min(sum(list(zip(*blr))[0]),ans+min(cand)))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
n,x = map(int,input().split())
blr = [list(map(int,input().split())) for i in range(n)]
tad = [[(x-b)*r+b*l,(x-b)*r,b*l,i] for i,(b,l,r) in enumerate(blr)]
tad.sort(reverse=True)
tacc = list(accumulate(list(zip(*tad))[1]))
aacc = list(accumulate(list(zip(*tad))[2]))
p = -10**18
ans = 0
cand = []
for i in range(n):
  if tacc[i] >= aacc[n-1]-aacc[i] and p < 0:
    p = i
    ans += i*x
    if p == 0:
      ttot = 0
      atot = aacc[n-1]
    else:
      ttot = tacc[p-1]
      atot = aacc[n-1]-aacc[p-1]
    dif = atot-ttot
  if p >= 0:
    idx = tad[i][3]
    b,l,r = blr[idx]
    if dif <= tad[i][2]:
      cand.append((dif+l-1)//l)
    else:
      cand.append(b+(dif-b*l+r-1)//r)
print(min(sum(list(zip(*blr))[0]),ans+min(cand)))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
n,x = map(int,input().split())
blr = [list(map(int,input().split())) for i in range(n)]
tad = [[(x-b)*r+b*l,(x-b)*r,b*l,i] for i,(b,l,r) in enumerate(blr)]
tad.sort(reverse=True)
tacc = list(accumulate(list(zip(*tad))[1]))
aacc = list(accumulate(list(zip(*tad))[2]))
p = -10**18
ans = 0
cand = []
for i in range(n):
  if tacc[i] >= aacc[n-1]-aacc[i] and p < 0:
    p = i
    ans += i*x
    if p == 0:
      ttot = 0
      atot = aacc[n-1]
    else:
      ttot = tacc[p-1]
      atot = aacc[n-1]-aacc[p-1]
    dif = atot-ttot
  if p >= 0:
    idx = tad[i][3]
    b,l,r = blr[idx]
    if dif <= tad[i][2]:
      cand.append((dif+l-1)//l)
    else:
      cand.append(b+(dif-b*l+r-1)//r)
print(ans+min(cand))

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 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:
    SS=S
    mid=(high+low)//2
    ppp=mid//X
    qqq=mid%X
    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
    if SS>=0:
        high=mid
    else:
        low=mid
        
print(high)

Submission status: Wrong Answer

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

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

flag=[0]*N
ans=0
for i in range(N):
    SS=S+data[i][0]
    if SS<0:
        S=SS
        flag[data[i][1]]=1
        ans+=X
    else:
        break

num=float("inf")

for i in range(N):
    if flag[i]==1:
        continue
    b,l,u=blu[i]
    if (S+b*l)%u==0:
        a=b+(-S-b*l)//u
    else:
        a=b+(-S-b*l)//u+1
    if S%l==0:
        a=min(a,(-S)//l)
    else:
        a=min(a,(-S)//l+1)
    num=min(num,a)

ans+=num
print(ans)

Submission status: Wrong Answer

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

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

flag=[0]*N
ans=0
for i in range(N):
    SS=S+data[i][0]
    if SS<0:
        S=SS
        flag[data[i][1]]=1
        ans+=X
    else:
        break

num=float("inf")

for i in range(N):
    if flag[i]==1:
        continue
    b,l,u=blu[i]
    if (S+b*l)%u==0:
        a=b-(S+b*l)//u
    else:
        a=b-(S+b*l)//u+1
    if S%l==0:
        a=min(a,-S//l)
    else:
        a=min(a,-S//l+1)
    num=min(num,a)

ans+=num
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
N, M = map(int, input().split())
X = []
s = 0
for _ in range(N):
    b, l, u = map(int, input().split())
    t = M * u - (u - l) * b
    X.append((t, b, l, u))
    s += b * l

X = sorted(X, key = lambda x: -x[0])
A = [0] + [x[0] for x in X]
for i in range(1, N+1):
    A[i] += A[i-1]

def sum_excl(i, j):
    return A[j] if j <= i else A[j] - X[i][0]

def chk(i):
    t, bb, ll, uu = X[i]
    l, r = 0, N + 1
    while r - l > 1:
        m = (l + r) // 2
        if sum_excl(i, m) + t >= s:
            r = m
        else:
            l = m
    re = (r - (i < r)) * M
    rem = s - sum_excl(i, r)
    l, r = 0, M + 1
    while r - l > 1:
        m = (l + r) // 2
        if (m * uu - (uu - ll) * bb if m > bb else m * ll) >= rem:
            r = m
        else:
            l = m
    re += r
    return re

print(min(chk(i) for i in range(N)))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# 写経
# にぶたん不要の解法
# https://atcoder.jp/contests/agc034/submissions/5768266
# generatorを作って
# 外でminする


def accumulate(a):
    """初項0"""
    su = 0
    yield su

    for x in a:
        su += x
        yield su


def solve_agc034c():
    from bisect import bisect_left
    from collections import namedtuple
    from functools import lru_cache
    import sys
    input = sys.stdin.readline

    Test = namedtuple('Test', 'Aoki_score lower_bound upper_bound')

    Test.Merit = lambda self, Takahashi_score: \
        self.lower_bound * Takahashi_score if Takahashi_score <= self.Aoki_score \
            else self.upper_bound * Takahashi_score - (self.upper_bound - self.lower_bound) * self.Aoki_score
    # Test.Merit = lru_cache(maxsize=None)(Test.Merit)

    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.Merit(Takahashi_score=X), reverse=True)
    # 勝つ科目は重要度upper_bound,負ける科目は重要度lower_bound

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

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

    bi = bisect_left(acc, need)  # bi問目まで完答でneed以上を達成(bi:1-indexed)=bi問解けばよい
    ge_need = acc[bi]  # need以上を達成するのに要した点数
    lt_need = acc[bi - 1]  # need未満の最大値を達成するのに要した点数

    def generate_candidates():
        INF = 10 ** 20
        for i, p in enumerate(tests, start=1):
            # p: partially_solved_test
            if i < bi:
                rest = need - (ge_need - p.Merit(Takahashi_score=X))
            else:
                rest = need - lt_need

            if rest <= p.Merit(Takahashi_score=p.Aoki_score):
                # 科目p単体の所要点数はAoki君以下でよく,lower_boundで計算
                add_ = (rest + p.lower_bound - 1) // p.lower_bound
            else:
                # 科目p単体の所要点数はAoki君を超える必要があり,upper_boundで計算
                add_ = p.Aoki_score
                add_ += (rest - p.Merit(Takahashi_score=p.Aoki_score) + p.upper_bound - 1) // p.upper_bound

            if add_ > X:
                yield INF
            else:
                ret = X * (bi - 1) + add_
                yield ret

    gen = generate_candidates()
    res = min(gen)
    print(res)
    return


if __name__ == '__main__':
    solve_agc034c()

Submission status: Wrong Answer

Solution code:
# 写経
# にぶたん不要の解法
# https://atcoder.jp/contests/agc034/submissions/5768266
# generatorを作って
# 外でminする


def accumulate(a):
    """初項0"""
    su = 0
    yield su

    for x in a:
        su += x
        yield su


def solve_agc034c():
    from bisect import bisect_left
    from collections import namedtuple
    from functools import lru_cache
    import sys
    input = sys.stdin.readline

    Test = namedtuple('Test', 'Aoki_score lower_bound upper_bound')

    Test.Merit = lambda self, Takahashi_score: \
        self.lower_bound * Takahashi_score if Takahashi_score <= self.Aoki_score \
            else self.upper_bound * Takahashi_score - (self.upper_bound - self.lower_bound) * self.Aoki_score
    Test.Merit = lru_cache(maxsize=None)(Test.Merit)

    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.Merit(Takahashi_score=X), reverse=True)
    # 勝つ科目は重要度upper_bound,負ける科目は重要度lower_bound

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

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

    bi = bisect_left(acc, need)  # bi問目まで完答でneed以上を達成(bi:1-indexed)=bi問解けばよい
    ge_need = acc[bi]  # need以上を達成するのに要した点数
    lt_need = acc[bi - 1]  # need未満の最大値を達成するのに要した点数

    def generate_candidates():
        INF = 10 ** 20
        for i, p in enumerate(tests, start=1):
            # p: partially_solved_test
            if i < bi:
                rest = need - (ge_need - p.Merit(Takahashi_score=X))
            else:
                rest = need - lt_need

            if rest <= p.Merit(Takahashi_score=p.Aoki_score):
                # 科目p単体の所要点数はAoki君以下でよく,lower_boundで計算
                add_ = (rest + p.lower_bound - 1) // p.lower_bound
            else:
                # 科目p単体の所要点数はAoki君を超える必要があり,upper_boundで計算
                add_ = p.Aoki_score
                add_ += (rest - p.Merit(Takahashi_score=p.Aoki_score) + p.upper_bound - 1) // p.upper_bound

            if add_ > X:
                yield INF
            else:
                ret = X * (bi - 1) + add_
                yield ret

    gen = generate_candidates()
    res = min(gen)
    print(res)
    return


if __name__ == '__main__':
    solve_agc034c()

Submission status: Wrong Answer

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

import numpy as np

N,X = map(int,input().split())
B,L,U = np.array([input().split() for _ in range(N)],dtype=np.int64).T

target = (B*L).sum()

full_score = B*L + U*(X-B)
i = full_score.argsort()[::-1]
B = B[i]; L = L[i]; U = U[i]; full_score = full_score[i]
full_score_cum = full_score.cumsum()

def test(x):
    # 全部でx回勉強して、target以上の得点を得ることが可能
    q,r = divmod(x,X)
    # q科目をフルで埋めて、1科目はr点まで埋める
    q_part = np.zeros_like(B)
    if q >= 1:
        q_part[q:] = full_score_cum[q-1]
        q_part[:q] = full_score_cum[q] - full_score[:q]
    r_part = np.where(r<=B,L*r,B*L+(r-B)*U)
    return (q_part + r_part).max() >= target

left = 0
right = X*N

while left + 1 < right:
    mid = (left + right)//2
    if test(mid):
        right = mid
    else:
        left = mid

answer = right
print(answer)

Submission status: Wrong Answer

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

import numpy as np

N,X = map(int,input().split())
B,L,U = np.array([input().split() for _ in range(N)],dtype=np.int64).T

target = (B*L).sum()

full_score = B*L + U*(X-B)
i = full_score.argsort()[::-1]
B = B[i]; L = L[i]; U = U[i]; full_score = full_score[i]
full_score_cum = full_score.cumsum()

def test(x):
    # 全部でx回勉強して、target以上の得点を得ることが可能
    q,r = divmod(x,X)
    # q科目をフルで埋めて、1科目はr点まで埋める
    q_part = np.zeros_like(B)
    if q >= 1:
        q_part[q:] = full_score_cum[q-1]
    q_part[:q] = full_score_cum[q] - full_score[:q]
    r_part = np.where(r<=B,L*r,B*L+(r-B)*U)
    return (q_part + r_part).max() >= target

left = 0
right = X*N

while left + 1 < right:
    mid = (left + right)//2
    if test(mid):
        right = mid
    else:
        left = mid

answer = right
print(answer)

Submission status: Wrong Answer

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

scores_sorted = sorted(scores, reverse=True)
cum = []
for i in range(N):
    val, ind = scores_sorted[i]
    if i==0:
        val_cum, opponent_cum = 0, opponent
    else:
        val_cum, opponent_cum = cum[-1]
    b, l, u = blu[ind]
    cum.append((val_cum + val, opponent_cum - l*b))


def calc_X(k):
    ret = -opponent
    n = k // X
    m = k % X
    if n == N:
        return cum[n-1][0] - cum[n-1][1]

    for i in range(N):
        temp = 0
        b, l, u = blu[i]
        if n > 0:
            if scores[i][0] >= scores_sorted[n-1][0]:
                temp = cum[n][0] - scores[i][0] - (cum[n][1] + b*l)
            else:
               temp = cum[n-1][0] - cum[n-1][1]
        else:
            temp = -opponent
        if m > b:
            temp += m * u + l * b - u * b
        else:
            temp += m * l
        ret = max(ret, temp)
    return ret
        
left = 0
right = N*X

while right - left > 1:
    mid = (left + right) // 2
    if calc_X(mid) >= 0:
        right = mid
    else:
        left = mid

if calc_X(left) >= 0:
    print(left)
else:
    print(right)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import math

N, X = list(map(int,input().split()))
blu = []
for i in range(N):
    blu.append(list(map(int,input().split())))
    sa = blu[-1][0]*blu[-1][1] + (X - blu[-1][0])*blu[-1][2]
    blu[-1].append(sa)

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

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

benkyo = 0
for i in range(N):
    if min_score < blu[i][3]:
        break
    else:
        min_score -= blu[i][3]
        benkyo += X

def min_time(score, b, l, u):
    if score <= b*l:
        return math.ceil(score/l)
    else:
        scorerest = score - b*l
        return b + math.ceil(scorerest/u)


if min_score > 0:
    times = X
    for i in range(benkyo//X, N):
        if min_score > blu[i][3]:
            break

        if times > min_time(min_score, blu[i][0], blu[i][1], blu[i][2]):
            times = min_time(min_score, blu[i][0], blu[i][1], blu[i][2])

    benkyo+=times

print(benkyo)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import math

N, X = list(map(int,input().split()))
blu = []
for i in range(N):
    blu.append(list(map(int,input().split())))
    sa = blu[-1][0]*blu[-1][1] + (X - blu[-1][0])*blu[-1][2]
    blu[-1].append(sa)

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

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

benkyo = 0
for i in range(N):
    if min_score < blu[i][3]:
        break
    else:
        min_score -= blu[i][3]
        benkyo += X

def min_time(score, b, l, u):
    if score <= b*l:
        return math.ceil(score/l)
    else:
        scorerest = score - b*l
        return b + math.ceil(scorerest/u)


if min_score > 0:
    times = X
    for i in range(benkyo//X, N):
        if min_score > blu[i][3]:
            break
        a = min_time(min_score, blu[i][0], blu[i][1], blu[i][2])
        if times > a:
            times = a

    benkyo+=times

print(benkyo)