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:
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 = -1, 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 = -1, 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: Accepted

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


# class TestCaseReader:
#     def __init__(self):
#         self._gen = self.gen()
#
#     def gen(self):
#         import os
#         folder = r'XXX'
#         with open(os.path.join(folder, 'in.txt'), mode='r') as f:
#             for row in f:
#                 row = row.rstrip()
#                 yield row
#
#     def __call__(self):
#         return next(self._gen)


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

    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

    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問解けばよい
    if bi == 0:
        print(0)  # 追加した
        return

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

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

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

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

scores_sorted = sorted(scores, reverse=True)
cum = [scores_sorted[0][0]]
for i in range(1, N):
    cum.append(cum[-1] + scores_sorted[i][0])


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

    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] - opponent) - scores[i][0]
            else:
               temp = cum[n-1] - opponent
        else:
            temp = -opponent
        if m > b:
            temp += (m-b) * u + b * l
        else:
            temp += (m-b) * l + b * 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: Accepted

Solution code:
# using main() makes code faster from the point of view of "access to variables in global name-space"
# def main():

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

import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
# accumulate() returns iterator! to get list: list(accumulate())
from math import factorial, ceil, floor
def factorize(n):
    """return the factors of the Arg and count of each factor
    
    Args:
        n (long): number to be resolved into factors
    
    Returns:
        list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
    """
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def combinations_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    # TODO: How should I do when n - r is negative?
    if n < 0 or r < 0:
        raise Exception('combinations_count(n, r) not defined when n or r is negative')
    if n - r < r: r = n - r
    if r < 0: return 0
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combinations_with_replacement_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    if n < 0 or r < 0:
        raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
    elif n == 0:
        return 1
    else:
        return combinations_count(n + r - 1, r)
from bisect import bisect_left, bisect_right
from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from operator import itemgetter
# ex1: List.sort(key=itemgetter(1))
# ex2: sorted(tuples, key=itemgetter(1,2))
from functools import reduce
def chmin(x, y):
    """change minimum
    if x > y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current minimum value
        y (long): potential minimum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x > y:
        x = y
        return (x, True)
    else:
        return (x, False)
def chmax(x, y):
    """change maximum
    if x < y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current maximum value
        y (long): potential maximum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x < y:
        x = y
        return (x, True)
    else:
        return (x, False)

from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

# first create factorial_list
# fac_list = mod_factorial_list(n)
INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

""" initialize variables and set inputs
# initialize variables
    # to initialize list, use [0] * n
    # to initialize two dimentional array, use [[0] * N for _ in range(N)]
# set inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
# preprocessing
    # transpose = [x for x in zip(*data)]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
    # flat = [flatten for inner in data for flatten in inner]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
# calculate and output
    # output pattern
    # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
"""

# functions used
r = lambda: sys.stdin.readline().strip()
r_int = lambda: int(r())
R = lambda: list(map(int, r().split()))
Rfloat = lambda: list(map(float, r().split()))
Rtuple = lambda: tuple(map(int, r().split()))
Rmap = lambda: map(int, r().split())

""" how to treat input
# single int: int(r())
# single string: r()
# single float: float(r())
# line int: R()
# line string: r().split()
# line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
# lines int: [R() for _ in range(n)]
"""

# set inputs
# sys.stdin = open('sample.txt') # for test
N, X = R()
BLU = [R() for _ in range(N)]
BLUV = [(b, l, u, (b*l)+(X-b)*u) for (b, l, u) in BLU]
BLUV.sort(key=itemgetter(3), reverse=True)
Score_Aoki = sum([a*b for (a, b, _) in BLU])
AcV = list(accumulate([i for i in zip(*BLUV)][3]))

Ans = INF
BaseLeft = bisect_left(AcV, Score_Aoki)
for i, (b, l, u, v) in enumerate(BLUV):
    BR1 = BaseLeft
    BR2 = bisect_left(AcV, Score_Aoki + v)
    Remain = Score_Aoki
    Adjust = 0
    if i < BR1:
        BR1 = BR2
        Adjust = 1
        Remain += v
    if BR1 > 0:
        Remain -= AcV[BR1-1]

    if Remain > v:
        continue
    elif Remain >= b*l:
        Ans, _ = chmin(Ans, ceil((Remain-b*l)/u) + b + (BR1-Adjust)*X)
    else:
        Ans, _ = chmin(Ans, ceil(Remain/l) + (BR1-Adjust)*X)

print(Ans)

"""memo: how to use defaultdict of list
# initialize
Dic = defaultdict(list)
# append
Dic[x].append(y)
# for
for k, v in Dic.items():
"""


# if __name__ == '__main__':
#     main()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


class TestObj(object):

    def __init__(self, b, l, u, x):
        self.aokip = b
        self.minval = l
        self.maxval = u
        self.maxp = l * b + u * (x-b)

    def calc_point(self, r, x):
        return self.minval * min(self.aokip, r) + self.maxval * max(0, r - self.aokip)


def judge(tests, cum, n, k, x, thr):
    q = k // x
    r = k % x
    takap = 0

    if q >= n:
        return True

    for i in range(1,n+1):
        if i <= q:
            takap = max(takap, cum[q+1] - tests[i].maxp + tests[i].calc_point(r,x))

        else:
            takap = max(takap, cum[q] + tests[i].calc_point(r,x))

        if takap >= thr:
            return True

    return False


def binary_search(tests, x):
    n = len(tests) - 1

    thr = sum([ti.minval * ti.aokip for ti in tests])

    if thr == 0:
        return 0

    low = 0
    high = 10**18

    cum = []
    for ti in tests:
        if len(cum) > 0:
            cum.append(cum[-1] + ti.maxp)
        else:
            cum.append(0)

    while high - low > 1:
        mid = (high+low) // 2

        if judge(tests, cum, n, mid, x, thr):
            high = mid

        else:
            low = mid

    return high

n, x = li()
tests = []
for _ in range(n):
    b,l,u = li()
    tests.append(TestObj(b,l,u,x))

tests.sort(key=lambda x: x.maxp, reverse=True)
tests = [TestObj(0,0,0,x)] + tests
print(binary_search(tests, x))

Submission status: Accepted

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

b_total = 0
dblu = []
for b, l, u in blu :
    dblu.append((u*X-(u-l)*b, b, l, u))
    b_total += b * l
dblu.sort(reverse=True)

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

ret = float('inf')

def judge(mid) :
    q = mid // X
    r = mid % X
    for i in range(N) :
        d, b, l, u = dblu[i]

        if q < i :
            tmp = s[q]
        else :
            tmp = s[q+1] - d

        if r < b :
            tmp += r * l
        else :
            tmp += b * l + u * (r - b)

        if tmp >= b_total :
            return True
    return False

left, right = -1, N * X

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

print(right)

Submission status: Accepted

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

class Task:
    def __repr__(self):
        return str(self.__dict__)

    def time_toget_point(self, p):
        # p点とるのに必要な時間を返す
        if p >= self.max_minus:
            return math.ceil(self.b + (p - self.max_minus)/self.u)
        else:
            return math.ceil(p/self.l)

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

    for i in range(n):
        t = Task()
        t.b, t.l, t.u = map(int, input().split())
        t.max_minus = t.b * t.l
        t.eff = ((x-t.b)*t.u) + (t.b*t.l) # 重み最高にした時の勉強効率
        t_list.append(t)
        total_behind += t.max_minus

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

    # 何要素目まで上から取ると必要点数を超えるか
    import bisect
    for max_i in range(len(t_list)):
        if cumsum[max_i] > total_behind:
            break

    # 部分点を取るtaskをi番目と決めたときの、必要勉強時間を求める。その最小値が答えになる
    min_time = -1
    for i, t in enumerate(t_list):
        if i <= max_i:
            # 上からとるものにiが含まれるケースでは、上から max_i 要素目までのうち i 以外を取り、iから最適な値をとる
            rest_p = total_behind - (cumsum[max_i] - t.eff)
        else:
            # 上からとるものにiが含まれないケースでは単に上から max_i-1 要素目までとり、iから最適な個数とる
            # rest_p が task i でとれる点数を超える場合があるが、解にはならないので気にしなくてよい
            if max_i == 0:
                rest_p = total_behind
            else:
                rest_p = total_behind - cumsum[max_i-1]

        # task i で rest_p とるのに必要な時間を求める
        time = x * (max_i) + t.time_toget_point(rest_p)

        if min_time == -1 or min_time > time:
            min_time = time
    print(min_time)

solve()

Submission status: Accepted

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

debug = True
debug = False

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

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

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

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

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

        total_behind += t.max_minus
    dprint(total_behind)

    # 重み最高での勉強効率の降順に並び変え
    import numpy as np
    t_list = sorted(t_list, key=lambda t: t.eff, reverse=True)
    cumsum = list(np.cumsum([t.eff for t in t_list]))
    dprint(t_list)
    dprint(cumsum)

    # 何要素目まで上から取ると必要点数を超えるか
    import bisect
    for max_i in range(len(t_list)):
        if cumsum[max_i] > total_behind:
            break
    dprint("max_i:", max_i)

    # 部分点を取るtaskをi番目と決めたときの、必要勉強時間を求める。その最小値が答えになる
    min_time = -1
    for i, t in enumerate(t_list):
        if i <= max_i:
            # このケースでは上から max_i 要素目までのうち i 以外を取り、iから最適な値をとる
            rest_p = total_behind - (cumsum[max_i] - t.eff)

        else:
            # このケースでは単に上から max_i-1 要素目までとり、iから最適な個数とる
            # 必要時間がXを超える場合は解にならないが、気にしなくていい
            if max_i == 0:
                rest_p = total_behind
            else:
                rest_p = total_behind - cumsum[max_i-1]

        time = x * (max_i) + t.time_toget_point(rest_p)
        dprint(i, rest_p, time, min_time, t)
        if min_time == -1 or min_time > time:
            min_time = time
    print(min_time)

solve()

Submission status: Accepted

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

debug = True
debug = False

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

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

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

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

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

        total_behind += t.max_minus
    dprint(total_behind)

    # 重み最高での勉強効率の降順に並び変え
    import numpy as np
    t_list = sorted(t_list, key=lambda t: t.eff, reverse=True)
    cumsum = list(np.cumsum([t.eff for t in t_list]))
    dprint(t_list)
    dprint(cumsum)

    # 何要素目まで上から取ると必要点数を超えるか
    import bisect
    max_i = bisect.bisect_left(cumsum, total_behind)
    dprint("max_i:", max_i)

    # 部分点を取るtaskをi番目と決めたときの、必要勉強時間を求める。その最小値が答えになる
    min_time = -1
    for i, t in enumerate(t_list):
        if i <= max_i:
            # このケースでは上から max_i 要素目までのうち i 以外を取り、iから最適な値をとる
            rest_p = total_behind - (cumsum[max_i] - t.eff)

        else:
            # このケースでは単に上から max_i-1 要素目までとり、iから最適な個数とる
            # 必要時間がXを超える場合は解にならないが、気にしなくていい
            if max_i == 0:
                rest_p = total_behind
            else:
                rest_p = total_behind - cumsum[max_i-1]

        time = x * (max_i) + t.time_toget_point(rest_p)
        dprint(i, rest_p, time, min_time, t)
        if min_time == -1 or min_time > time:
            min_time = time
    print(min_time)

    # total_time = 0 # 総勉強時間
    # total_score = -1 * total_behind # マイナスからスタートし、0になったら勝ち
    # for i, t in enumerate(t_list):
    #     # ためしに全力してみる
    #     total_score_tmp = total_score
    #     total_score_tmp += t.eff
    #
    #     if total_score_tmp < 0:
    #         # まだ勉強が足りないので、このtaskをコミットして勉強を続ける
    #         total_score = total_score_tmp
    #         total_time += x
    #         dprint(i, total_score, total_time, "commited")
    #     else:
    #         # これを全力すると勉強しすぎの場合、いったん中止
    #         dprint(i, total_score, total_time, t.eff, "stop")
    #         break
    #
    # # 残り必要点数を稼ぐのにもっとも効率がいいものを探す
    # dprint("ajusting", total_time, total_score)
    #
    # min_rest_time = -1 # 残りを稼ぐ最小勉強時間
    # for t in t_list[i:]:
    #     rest_time = t.time_toget_point(-1*total_score)
    #     if min_rest_time == -1 or rest_time < min_rest_time:
    #         min_rest_time = rest_time
    #
    # print(int(total_time + min_rest_time))


solve()

Submission status: Accepted

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

def solve():
    N, X = map(int, input().split())
    tests = []
    D0 = 0
    for _ in range(N):
        B, L, U = map(int, input().split())
        v = L*B + U*(X-B)
        tests.append((v, B, L, U))
        D0 -= L*B
    tests.sort(reverse=True)
    accVs = list(accumulate([0] + tests, lambda accX, X: accX + X[0]))

    def isOK(k):
        q = k // X
        r = k % X
        accV = accVs[q+1]
        for v, B, L, U in tests[:q]:
            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, B, L, U in tests[q:]:
            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


print(solve())

Submission status: Accepted

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)

accV = 0
accVs = [0]
for v, i in vs:
    accV += v
    accVs.append(accV)
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: Accepted

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

def solve():
    N, X = map(int, input().split())
    tests = []
    D0 = 0
    for _ in range(N):
        B, L, U = map(int, input().split())
        v = L*B + U*(X-B)
        tests.append((v, B, L, U))
        D0 -= L*B
    tests.sort(reverse=True)

    accV = 0
    accVs = [0]
    for v, B, L, U in tests:
        accV += v
        accVs.append(accV)

    def isOK(k):
        q = k // X
        r = k % X
        accV = accVs[q+1]
        for v, B, L, U in tests[:q]:
            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, B, L, U in tests[q:]:
            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


print(solve())

Submission status: Accepted

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

from bisect import bisect_right, bisect_left

def main():
    N, X = LI()
    b_l_u = []
    for i in range(N):
        b_l_u.append(LI())

    sum_of_test = [ (b_l_u_i[1]*b_l_u_i[0]+b_l_u_i[2]*(X-b_l_u_i[0]), i) for i,b_l_u_i in enumerate(b_l_u)]
    sum_of_test.sort(reverse=True)  # O(nlogn)

    cumsum_of_test = []
    tmp = 0
    for i in sum_of_test:  # O(n)
        tmp += i[0]
        cumsum_of_test.append(tmp)

    B = sum([l*b for b, l, u in b_l_u])  # O(n)
    head = bisect_right(cumsum_of_test, B)-1
    cumsum = cumsum_of_test[head]


    take_li = []
    for j, (sum_, i) in enumerate(sum_of_test):  # O(N)
        # cumsum の中に入っていたら、引く。
        if j <= head:
            new_head = bisect_right(cumsum_of_test, B+sum_)-1  # O(log N)
            new_cumsum = cumsum_of_test[new_head] - sum_
            left = B - new_cumsum
            take_1 = X * new_head
        else:
            left = B - cumsum
            take_1 = X*(head+1)

        if head==-1:  # i番目を下からとっていくコードのみでOK.
            left = B
            take_1 = 0

        b, l, u = b_l_u[i]
        from math import ceil
        if left/l <= b:
            take = ceil(left/l)
        else:
            take = b + ceil((left - b*l)/u)

        if take > X: continue

        take_li.append(take+take_1)

    print(min(take_li))

main()