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

Solution code:
N,X=map(int,input().split())
data=[0]*N
A=[0]*N
zero=0
for i in range(N):
    b,l,u=map(int,input().split())
    zero-=l*b
    data[i]=(b,l,u)
    A[i]=(i,(X-b)*u+b*l)
A.sort(key=lambda x:x[1],reverse=True)
S=[0]*N
idx=[0]*N
for i,a in enumerate(A):
    S[i]=S[i-1]+a[1]
    idx[a[0]]=i
def check(k):
    q=k//X
    r=k-q*X
    for i in range(N):
        b,l,u=data[i]
        if q==0:
            now=zero
        elif idx[i]<q:
            now=zero+S[q]-A[idx[i]][1]
        else:
            now=zero+S[q-1]
        if r<=b:
            now+=r*l
        else:
            now+=(r-b)*u+b*l
        if now>=0:
            return True
    return False
Mincan=N*X
Maxcant=-1
c=(1,2)
while True:
    if Maxcant+1==Mincan:
        ans=Mincan
        break
    x=N*X*c[0]//c[1]
    if check(x):
        if Mincan>x:
            Mincan=x
            c=(c[0]*2-1,c[1]*2)
    else:
        if Maxcant<x:
            Maxcant=x
            c=(c[0]*2+1,c[1]*2)
print(ans)

Submission status: Accepted

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]

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

print(ok)

Submission status: Accepted

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,i))
    pt -= l*b

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

ans = []
reached = False
sum = 0
while len(blu)>0:
    mv,s,t,b,l,u,r = 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:
        ans.append((s,b,l,u))
        pt = nxtpt
        sum += t
        continue
    elif nxtpt == 0: # < (u if pt+l*b<0 else l):
        if not reached:
            ans.append((s,b,l,u))
            pt2 = pt + u*x - u*b + l*b
        sum += t
        break
    else:  # nxtpt > 0
        m = pt + l*b
        ddprint("m {}".format(m))
        if m>=0:
            t = (-pt+l-1)//l
        else:
            m = -m
            t = b + (m+u-1)//u
        if not reached:
            ans.append((s,b,l,u))
            pt2 = pt + u*x - u*b + l*b
            reached = True
        s = -pt
        ddprint("s/t {} s {} t {}".format(s/t,s,t))
        heapq.heappush(blu, (-s/t,s,t,b,l,u,-1))

sum2 = x * (len(ans)-1)
for z in ans[:-1]:
    s,b,l,u = z
    pt = pt2 - s
    m = pt + l*b
    if m>=0:
        t = (-pt+l-1)//l
    else:
        t = b+(-m+u-1)//u
    if sum2+t < sum:
        sum = sum2+t
print(sum)

Submission status: Accepted

Solution code:
import math
class Test:
    pass
n, x = map(int, input().split())
l = []
lose = 0
for _ in range(n):
    t = Test()
    t.b, t.l, t.u = map(int, input().split())
    t.total = t.b * t.l + (x - t.b) * t.u
    l.append(t)
    lose += t.b * t.l
l = sorted(l, key=lambda t: t.total, reverse=True)

sum_upto_i = 0
for i, ti in enumerate(l):
    sum_upto_i += ti.total
    if sum_upto_i >= lose:
        break

min_needed = x
for j, tj in enumerate(l):
    if j <= i:
        lose_left = lose - (sum_upto_i - tj.total)
    else:
        lose_left = lose - (sum_upto_i - ti.total)
    if tj.b * tj.l < lose_left:
        lose_left -= tj.b * tj.l
        if (x - tj.b) * tj.u < lose_left:
            continue
        else:
            needed = tj.b + math.ceil(lose_left / tj.u)
    else:
        needed = math.ceil(lose_left / tj.l)
    if min_needed > needed:
        min_needed = needed
print(x * i + min_needed)

Submission status: Accepted

Solution code:
n, x = list(map(int, input().split()))

exms = []
nrm = 0

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

for i, line in enumerate(lines):
    b, l, u = line
    exms.append((u * x - b * (u - l), b, l, u, i))
    nrm += b * l
exms_sorted = sorted(exms, reverse=True)


remain_nrm = nrm

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

if sub_d == -1:
    print(n * x)
    exit()

base_ans = i * x
base_remain_nrm = remain_nrm

ans = 10 ** 10

for d, b, l, u, i in exms:
    if i in used:
        curr_remain_nrm = base_remain_nrm + d - sub_d
    else:
        curr_remain_nrm = base_remain_nrm

    if curr_remain_nrm <= b * l:
        extra = (curr_remain_nrm - 1) // l + 1
    else:
        extra = (curr_remain_nrm + b * (u - l) - 1) // u + 1
    if extra > x:
        continue
    ans = min(ans, base_ans + extra)

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/agc034/submissions/5758268
from itertools import accumulate
from operator import itemgetter

inf = float('inf')

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

bs = []
ls = []
us = []
values = []

loss = 0
for idx in range(N):
    b, l, u = map(int, input().split())
    value = X * u - b * (u - l)

    bs.append(b)
    ls.append(l)
    us.append(u)
    values.append(value)

    loss += b * l

order = [idx for idx, _ in sorted(enumerate(values), key=itemgetter(1), reverse=True)]

pref = [0] + list(accumulate(values[idx] for idx in order))

ans = inf
for it in range(N):
    i = order[it]
    for coeff in ls[i], us[i]:
        low = 0
        high = N
        while low <= high:
            mid = (low + high) >> 1
            cur = loss
            if coeff == us[i]:
                cur += bs[i] * (us[i] - ls[i])
            can_get = pref[mid]
            vals = mid
            if it < mid:
                can_get -= values[i]
                vals -= 1
            can_get += X * coeff
            if can_get >= cur:
                can_get -= X * coeff
                need = 0
                if can_get < cur:
                    need = (cur - can_get + coeff - 1) // coeff
                ans = min(ans, vals * X + need)
            if low == high:
                break
            if can_get >= cur:
                high = mid
            else:
                low = mid + 1
print(ans)

Submission status: Accepted

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

    border = N - perfects
    ret = []
    if len(B[:border]) > 0:
        # 途中まで頑張るやつを 0 点エリアから選択
        ret.append(max(
            scores_cumsum[border] +
            np.minimum(half_x, B[:border]) * L[:border] + np.maximum(0, half_x - B[:border]) * U[:border]
        ))
    if len(B[border:]) > 0:
        # 途中まで頑張るやつを満点エリアから選択
        ret.append(max(
            scores_cumsum[border - 1] - scores[border:] +
            np.minimum(half_x, B[border:]) * L[border:] + np.maximum(0, half_x - B[border:]) * U[border:]
        ))
    return max(0, *ret)


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

Submission status: Accepted

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
    else:
        if c_adv[x_subject_count] + 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: Accepted

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

left1 = left - c[c_p]
ans1 = 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)
ans2 = 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 + np.concatenate((ans1, ans2)).min())

Submission status: Accepted

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[c_p:] = np.where(left <= bl[c_p:], (left - 1) // l[c_p:] + 1, (left - bl[c_p:] - 1) // u[c_p:] + b[c_p:] + 1)
ans1 = c_p * X + ans.min()
print(ans1)

Submission status: Accepted

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)

if sub_d == -1:
    print(n * x)
    exit()

base_ans = i * x
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: Accepted

Solution code:
import sys
from bisect import bisect_left
from itertools import accumulate
from operator import itemgetter

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)
exams_acc = list(accumulate(map(itemgetter(0), exams_sorted)))
exams_loc = {i: loc for loc, i in enumerate(map(itemgetter(4), exams_sorted))}
# print(norma)
# print(exams_sorted)
# print(exams_acc)

ans = 10 ** 10
base_loc = bisect_left(exams_acc, norma)
base_ans = base_loc * x
base_remain_norma = norma - exams_acc[base_loc - 1] if base_loc > 0 else norma
# print(f'base_remain_norma:{base_remain_norma}')
for d, b, l, u, i in exams:
    exam_loc = exams_loc[i]
    if base_loc <= exam_loc:
        curr_ans = base_ans
        curr_remain_norma = base_remain_norma
    else:
        tmp_norma = norma + d
        tmp_loc = bisect_left(exams_acc, tmp_norma)
        curr_ans = (tmp_loc - 1) * x
        curr_remain_norma = tmp_norma - exams_acc[tmp_loc - 1]
    if curr_remain_norma <= b * l:
        extra = (curr_remain_norma - 1) // l + 1
    else:
        extra = (curr_remain_norma + b * (u - l) - 1) // u + 1
    # print(d, b, l, u, i)
    # print(f'exl:{exam_loc}  {int(base_loc <= exam_loc)}  norma:{curr_remain_norma}  curans:{curr_ans}  '
    #       f'extra:{extra}')
    if extra > x:
        continue
    ans = min(ans, curr_ans + extra)

print(ans)

Submission status: Accepted

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(full_score_list[i][1])
    t_score += full_score_list[i][0]
    if t_score >= s_score:
        last_index = full_score_list[i][1]
        surplus = t_score - s_score
        shortage = s_score - t_score + full_score_list[i][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.ceil(shortage / l)))
    elif b*l + (x-b)*u >= shortage:
        min_promotion = min(min_promotion, b + int(math.ceil((shortage - b*l) / u)))
ans = min(ans, min_promotion + x * len(full_score_set))
print(ans)

Submission status: Accepted

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
if judge(0):
    r=0
while l+1<r:
    k=(l+r)//2
    if judge(k):
        r=k
    else:
        l=k
print(r)

Submission status: Accepted

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
if score_needed == 0:
    print(0)
    exit()
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: Accepted

Solution code:
from itertools import accumulate,chain



def max_merit(b,l,u):
    return u*(X-b) + l*b

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

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

blu = list(tuple(map(int,input().split())) for _ in range(N))
required = sum(l*b for b,l,u in blu)
blu = sorted(((max_merit(*x), x) for x in blu), reverse=True)


for mi,x in enumerate(accumulate(m for m,_ in blu)):
    if x >= required:
        msum2 = x
        msum1 = x - blu[mi][0]
        break

def helper():
    for i,(m,x) in enumerate(blu):
        if i >= mi:
            r = required - msum1
        else:
            r = required + m - msum2

        b,l,u = x
        if r <= l*b:
            yield mi*X + (r-1)//l + 1
        else:
            r -= l*b
            yield mi*X + b + (r-1)//u + 1

print(min(helper()))

Submission status: Accepted

Solution code:
import math

def main():
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    X = int(buflist[1])
    iblu = []
    for i in range(N):
        buf = input()
        buflist = buf.split()
        iblu.append((i, int(buflist[0]), int(buflist[1]), int(buflist[2])))
    aoki_score = 0
    takahashi_score = 0
    for x in iblu:
        aoki_score += x[1] * x[2]
    score_gain = []
    for x in iblu:
        score_gain.append((x[0], X * x[3] - x[1] * (x[3] - x[2])))
    score_gain.sort(reverse=True, key=lambda x: x[1])
    study_hour = 0
    for i, x in enumerate(score_gain):
        new_takahashi_score = takahashi_score + x[1]
        if new_takahashi_score < aoki_score:
            study_hour += X
            takahashi_score = new_takahashi_score
        else: # new_takahashi_score >= aoki_score
            score_needed = aoki_score - takahashi_score
            study_minimum = X
            for j in range(i, N):
                penalty = iblu[score_gain[j][0]][1] * (iblu[score_gain[j][0]][3] - iblu[score_gain[j][0]][2])
                st = min(math.ceil(score_needed / iblu[score_gain[j][0]][2]), math.ceil((score_needed + penalty) / iblu[score_gain[j][0]][3]))
                if st < study_minimum:
                    study_minimum = st
            for j in range(i):
                score_needed = aoki_score - new_takahashi_score + score_gain[j][1]
                penalty = iblu[score_gain[j][0]][1] * (iblu[score_gain[j][0]][3] - iblu[score_gain[j][0]][2])
                st = min(math.ceil(score_needed / iblu[score_gain[j][0]][2]), math.ceil((score_needed + penalty) / iblu[score_gain[j][0]][3]))
                if st < study_minimum:
                    study_minimum = st
            #penalty = iblu[x[0]][1] * (iblu[x[0]][3] - iblu[x[0]][2])
            #study_hour += min(math.ceil(score_needed / iblu[x[0]][2]), math.ceil((score_needed + penalty) / iblu[x[0]][3]))
            #takahashi_score += iblu[x[0]][2] * math.ceil(score_needed / iblu[x[0]][2]) if math.ceil(score_needed / iblu[x[0]][2]) < math.ceil((score_needed + penalty) / iblu[x[0]][3]) else iblu[x[0]][3] * math.ceil((score_needed + penalty) / iblu[x[0]][3]) - penalty
            study_hour += study_minimum
            takahashi_score = new_takahashi_score
        if takahashi_score >= aoki_score:
            break
    print(study_hour)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

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

for b,l,u,m in BLU[:i]:
    h = min(h,solve(b,l,u,-s-BLU[i][3]+m))

ans += h
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

a, i = A[iaaaa]
aoki_ -= a
#aoki_ = -aoki
anss = (iaaaa)*X
mi = float("inf")
for a, i in A[:iaaaa]:
    b, l, u = S[i]
    aoki = aoki_ + a
    an, m = divmod(aoki, l)
    if m!=0:
        an += 1
    mi = min(mi, an)
    aoki += (u-l) * b
    an, m = divmod(aoki, u)
    if m!=0:
        an += 1
    mi = min(mi, an)

print(min(ans_, anss+mi))

Submission status: Accepted

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

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

if l_sum==0:
    print(0)
else:
    data=sorted(data,key=lambda x:x[3],reverse=True)
    
    S=[-l_sum]
    s=-l_sum
    for i in range(N):
        s += data[i][3]
        S.append(s)
    
    def judge(P):
    
        n=P//X
        p=P%X
    
        if S[n]>=0:
            return True
        else:
            new_list = []
            for i in range(N):
                if i>=n:
                    b,l,u,x = data[i]
                    if p>=b:
                        new_list.append(u*(p-b)+l*b)
                    else:
                        new_list.append(l*p)
                else:
                    b,l,u,x = data[i]
                    new_list.append(max(u*(p-X),l*p-u*X+b*(u-l))+data[n][3])
                    
            if S[n] + max(new_list)>=0:
                return True
            else:
                return False
    
    max_P=N*X
    
    def bisect(m,M):
        if M-m==1:
            return M
        else:
            if judge((m+M)//2):
                return bisect(m,(m+M)//2)
            else:
                return bisect((m+M)//2,M)
    
    print(bisect(0,max_P))

Submission status: Runtime Error

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 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
        #print (np)
        ansplus = min(ansplus , np)
else:
    ansplus = 0

print (ans + ansplus)

Submission status: Runtime Error

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

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
flg = 1
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
  if dif >= 0 and anstmp < ans:
    flg = 1
  elif anstmp < ans:
    flg = 0
  ans = min(ans,anstmp)
if flg == 0:
  print(2/0)
print(ans)