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

Solution code:
from collections import deque
from heapq import *
n,x=map(int,input().split())
qlist=[]
for iii in range(n):
  qlist.append(list(map(int,input().split())))

qlist.sort(key=lambda x:x[2],reverse=True)
qlist=deque(qlist)
coverH=0
coverL=0
cnttime=0
lmax=[]
hmin=[]
while len(qlist)>0:
  q1=qlist.popleft()
  coverH+=(x-q1[0])*q1[2]
  cnttime+=x
  heappush(hmin,[q1[2],q1[0]])
  while (coverH>coverL) and (len(qlist)>0):
    q2=qlist.pop()
    coverL+=q2[0]*q2[1]
    heappush(lmax,[-q2[1],q2[0]])
if coverH>=coverL:
  z=heappop(hmin)
  cnttime-=(coverH-coverL)//z[1]
  print(cnttime)
else:
  while coverL>coverH and lmax:
    z=heappop(lmax)
    if (coverL-coverH)//(-z[0]) <= x-z[1]:
      if (coverL-coverH)%(-z[0])==0:
        cnttime+=(coverL-coverH)//(-z[0])
      else:
        cnttime+=(coverL-coverH)//(-z[0])+1
      print(cnttime)
    else:
      cnttime+=x-z[1]
      coverL+=z[0]*(x-z[1])

Submission status: Runtime Error

Solution code:
import bisect


n, x = map(int, input().split())
tests = []
targets = []
low_costs = []
need_point = 0
for i in range(n):
    b, l, u = map(int, input().split())
    tests.append((b, l, u))
    targets.append((u*x-(u-l)*b, i))
    low_costs.append((b, -u, (-(u*x-(u-l)*b), i)))
    need_point += l*b
targets.sort(reverse=True)
low_costs.sort()

if n == 1:
    print(tests[0][0])
    exit()

ranks = [0]*n

total_cost = 0
total_point = 0
point_sum = []
for i in range(n):
    # 何番目に大きいかを記録
    ranks[targets[i][1]] = i
    total_point += targets[i][0]
    total_cost += x
    point_sum.append(total_point)


def want_n_point(n, b, l, u):
    if n/l < b:
        return (n+l-1)//l
    else:
        m = n + (u-l)*b
        return (m + u - 1)//u


j = bisect.bisect_right(point_sum, need_point)
if j == 0:
    min_cost = float('inf')
    for i in range(n):
        b,l,u = tests[i]
        cost = want_n_point(need_point, b,l,u)
        min_cost = min(min_cost, cost)
    print(min_cost)
    exit()

        
if point_sum[j] == need_point:
    min_cost = x * j
else:
    min_cost = x*(j+1)


# print('need: ', need_point)
# print('point_sum:', point_sum)
# print('min_cost', min_cost)

for i in range(n):
    r = ranks[i]
    b, l, u = tests[i]
    max_point = u*x - (u-l)*b

    # ps=[10, 100, 200], max_point=50, need_point(120)
    # 120-50 = 70はj=1の位置に挿入される大きさ。
    # j番目までの合計(100)にmax_point(50)を足すとneed_point(120)を超える
    j = bisect.bisect_right(point_sum, need_point-max_point)
    husoku = need_point - point_sum[j]

    # print('max_point:', max_point)
    # print('j:', j)
    if r <= j:
        # ほんまか？
        # print(r, i,'***continue***')
        continue
    # print('husoku', husoku)
    # print('(j+1)*x:', (j+1)*x)
    # print('want_n_point(husoku, b, l, u)',want_n_point(husoku, b, l, u))
    cost = (j+1)*x + want_n_point(husoku, b, l, u)
    min_cost = min(min_cost, cost)
    # print(r, i, cost, min_cost)

print(min_cost)

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))
def binary_search_loop(l):
	global su,cp,p,a
	arry = list(range(l+1))
	left = 0
	right = len(arry) - 1
	while left <= right:
		mid = (left + right) // 2
		if left == right:
			return mid              
		elif arry[mid] <= -(-(su - cp)//(p-a[i][0])):
			right = mid
		else:
			left = mid + 1


n,p = m()

a = []

for i in range(n):
	a.append(l())


a.sort(reverse = True,key = lambda x:(p - x[0])*x[2])
su = 0
cp = 0
coun = 0
for i in range(n):
	su += a[i][0]*a[i][1]

for i in range(n):
	su -= a[i][0]*a[i][1]
	if cp + a[i][2] * p == su + a[i][0]*a[i][2]:
		coun += p
		break
	elif cp + a[i][2] * p <  su + a[i][0]*a[i][2]:
		cp += a[i][2] * p
		su += a[i][0]*a[i][2]
		coun += p
	else:
		ppp = binary_search_loop(a[i][2])
		ppp = -(-(su - cp)//(ppp)) + a[i][0]
		coun += ppp
		break

print(coun)

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))
def binary_search_loop(l):
	global su,cp,p,a
	arry = list(range(l+1))
	left = 0
	right = len(arry) - 1
	while left <= right:
		mid = (left + right) // 2
		print(mid)
		if left == right:
			return mid              
		elif arry[mid] < (su - cp)//(p-a[i][0]):
			right = mid - 1
		else:
			left = mid + 1


n,p = m()

a = []

for i in range(n):
	a.append(l())


a.sort(reverse = True,key = lambda x:(p - x[0])*x[2])
su = 0
cp = 0
coun = 0
for i in range(n):
	su += a[i][0]*a[i][1]

for i in range(n):
	su -= a[i][0]*a[i][1]
	if cp + a[i][2] * p == su + a[i][0]*a[i][2]:
		coun += p
		break
	elif cp + a[i][2] * p <  su + a[i][0]*a[i][2]:
		cp += a[i][2] * p
		su += a[i][0]*a[i][2]
		coun += p
	else:
		ppp = binary_search_loop(a[i][2])
		print(ppp)
		ppp = -(-(su - cp)//(ppp)) + a[i][0]
		coun += ppp
		break

print(coun)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
s = sys.stdin.readlines()
N, X = map(int, s[0].split())
score_dict = {}
blue_score = 0
taka_score = 0
for e in s[1:N + 1]:
    b, l, u = map(int, e.split())
    score = X * u - b * (u - l)
    if u in score_dict:
        score_dict[score] = score_dict[score].append(l)
    else:
        score_dict[score] = [l]
    blue_score += b * l

time = 0
comp_flg = 0
tmp_time = 10 ** 9
for score, l_list in sorted(score_dict.items(), key=lambda x: -x[0]):
    l_list.sort()
    for l in l_list:
        if blue_score - taka_score - score > 0:
            taka_score += score
            time += X
        else:
            if tmp_time > -(-(blue_score - taka_score) // l):
                tmp_time = -(-(blue_score - taka_score) // l)
                comp_flg = 1
                break
    if comp_flg == 1:
        break
if tmp_time != 10 ** 9:
    time += tmp_time
print(int(time))

Submission status: Runtime Error

Solution code:
import math

n, x = map(int, input().split())
tests_raw = []
tmps = 0
time = 0
for _ in range(n):
  test = list(map(int, input().split()))
  tmp = test[0] * test[1]
  tmps += tmp
  test.append((x-test[0])*test[2]+tmp)
  tests_raw.append(test)
tests = sorted(tests_raw, key = lambda x: x[3], reverse=True)
#print(tmps)
#print(tests)

while tmps >= tests[0][3]:
  test = tests.pop(0)
  tmps -= test[3]
  time += x
#  print(test)

rem_min = x
for test in tests:
  reml = math.ceil(tmps/test[1])
  remu = math.ceil((tmps+(test[2]-test[1])*test[0])/test[2])
  rem_min = min(rem_min, reml, remu)
  
print(time+rem_min)

Submission status: Runtime Error

Solution code:
from heapq import *
n,x=map(int,input().split())
blu=[list(map(int,input().split())) for i in range(n)]
ans=0
s=[]
t=0
for i,j in enumerate(blu):
    b,l,u=j
    t+=b*l
    heappush(s,(-(u*(x-b)+l*b),i))
while 1:
    i=heappop(s)
    a,b=i
    if(t+a<0):
        break
    else:
        t+=a
        blu[b]=0
        ans+=x
s=[]
fa=x
tmp=ans
for i in blu:
    if(i!=0):
        b,l,u=i
        heappush(s,(-l,b,u))
        if(t>l*b):
            fa=min(fa,b-((l*b-t)//u))
        else:
            fa=min(fa,-(-t//l))
while 1:
    i=heappop(s)
    if(len(i)==3):
        l,b,u=i
        if(t+l*b>0):
            t+=l*b
            ans+=b
            heappush(s,(-u,b))
        else:
            ans+=-(-t//-l)
            break
    else:
        u,b=i
        if(t+u*(x-b)>0):
            t+=u*(x-b)
            ans+=x-b
        else:
            ans+=-(-t//-u)
            break
print(min(ans,fa+tmp))

Submission status: Runtime Error

Solution code:
from heapq import *
n,x=map(int,input().split())
blu=[list(map(int,input().split())) for i in range(n)]
ans=0
s=[]
t=0
for i,j in enumerate(blu):
    b,l,u=j
    t+=b*l
    heappush(s,(-(u*(x-b)+l*b),i))
while 1:
    i=heappop(s)
    a,b=i
    if(t+a<0):
        break
    else:
        t+=a
        blu[b]=0
        ans+=x
s=[]
fa=x
tmp=ans
for i in blu:
    if(i!=0):
        b,l,u=i
        heappush(s,(-l,b,u))
        if(t>=l*b):
            fa=min(fa,b-((l*b-t)//u))
while 1:
    i=heappop(s)
    if(len(i)==3):
        l,b,u=i
        if(t+l*b>0):
            t+=l*b
            ans+=b
            heappush(s,(-u,b))
        else:
            ans+=-(-t//-l)
            break
    else:
        u,b=i
        if(t+u*(x-b)>0):
            t+=u*(x-b)
            ans+=x-b
        else:
            ans+=-(-t//-u)
            break
print(min(ans,fa+tmp))

Submission status: Runtime Error

Solution code:
import math
n, x = map(int, input().split())
blu = [list(map(int, input().split())) for _ in range(n)]
f = lambda y:(x-y[0])*y[2]+y[1]*y[0]
blu = sorted(blu, key = f, reverse = True)
B = 0
for i in range(n):
    b, l, u = blu[i]
    B+=b*l
i=0
ans = 0
while True:
    tmp = f(blu[i])
    if B>=tmp:
        B-=tmp
        ans+=x
    else:
        break
    i+=1
k=x
for j in range(i, n):
    b, l, u = blu[j]
    k = min(math.ceil(B/l), math.ceil((B+(u-l)*b)/l), k)
print(ans+k)

Submission status: Runtime Error

Solution code:
n, x = map(int, input().split())
blu = [list(map(int, input().split())) for _ in range(n)]
f = lambda y:(x-y[0])*y[2]+y[1]*y[0]
blu = sorted(blu, key = f, reverse = True)
B = 0
for i in range(n):
    b, l, u = blu[i]
    B+=b*l
i=0
ans = 0
while True:
    tmp = f(blu[i])
    if B>=tmp:
        B-=tmp
        ans+=x
    else:
        break
    i+=1
k=x
for j in range(i, n):
    b, l, u = blu[j]
    k = min(math.ceil(B/l), math.ceil((B+(u-l)*b)/l), k)
print(ans+k)

Submission status: Runtime Error

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]=(b*l+(X-b)*u)
    data[i]=(i,b,l,u)
    under[i]=(i,l*b)
    
    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
ansM=i
nowM=now
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 and M0<M:
            M=M0
            ansM=i
            nowM=now0-(M0-b)*u
    elif M0<M:
        M=M0
        ansM=i
        nowM=now-M0*l
ans+=M
nowM*=-1
check=[data[i] for i in used|{ansM}]
check.sort(key=lambda x:x[2])
idx=0
while idx<len(check):
    if nowM-check[idx][2]>=0:
        nowM-=check[idx][2]
        ans-=1
    else:
        idx+=1
print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush

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

b_list = [0]*N
l_list = [0]*N
u_list = [0]*N

for i in range(N):
    b, l, u = map(int, input().split())
    b_list[i] = b
    l_list[i] = l
    u_list[i] = u

# lose weight
lose_weight = sum([b_list[i]*l_list[i] for i in range(N)])

# win weight
win_weight = [(X - b_list[i])*u_list[i]+b_list[i]*l_list[i] for i in range(N)]

h = []
for i in range(N):
    heappush(h, (-win_weight[i], i))

used_flg = [0]*N
res = 0
while True:
    win, i = heappop(h)
    if win + lose_weight < 0:
        break
    elif win + lose_weight == 0:
        res += X
        used_flg[i] = 1
        lose_weight = 0
        break
    else:
        res += X
        used_flg[i] = 1
        lose_weight += win

r_min = X
for i in range(N):
    if used_flg[i] == 0:
        if lose_weight > b_list[i]*l_list[i]:
            p = lose_weight - b_list[i]*l_list[i]
            q = u_list[i]
            if p % q == 0:
                r = p // q + b_list[i]
            else:
                r = p // q + b_list[i] + 1
            if r < r_min:
                r_min = r
        else:
            p = lose_weight
            q = l_list[i]
            if p % q == 0:
                r = p // q
            else:
                r = p // q + 1
            if r < r_min:
                r_min = r

print(res + r)

Submission status: Runtime Error

Solution code:
import math
n, x = map(int, input().split())
blu = [list(map(int, input().split())) for _ in range(n)]
f = lambda y:(x-y[0])*y[2]+y[1]*y[0]
blu = sorted(blu, key = f, reverse = True)
B = 0
for i in range(n):
    b, l, u = blu[i]
    B+=b*l
i=0
ans = 0
while True:
    tmp = f(blu[i])
    if B>=tmp:
        B-=tmp
        ans+=x
    else:
        b, l, u = blu[i]
        ans+=min(math.ceil((B+b*(u-l))/u), math.ceil((B/l)))
        break
    i+=1
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

#define MIN_INT -2147483648
#define MAX_INT 2147483647
#define MIN_LONG -9223372036854775808L
#define MAX_LONG 9223372036854775807L

#define long long long int

using namespace std;

// @author: pashka

int main() {
    ios::sync_with_stdio(false);

    int n;
    long x;
    cin >> n >> x;
    vector<long> l(n), r(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> b[i] >> l[i] >> r[i];
    }

    long s = 0;
    for (int i = 0; i < n; i++) {
        s += l[i] * b[i];
    }

    long L = -1;
    long R = x * n;
    while (R > L + 1) {
        long M = (L + R) / 2;
        vector<pair<long, int>> z(n);
        for (int i = 0; i < n; i++) {
            z[i] = {x * r[i] - (r[i] - l[i]) * b[i], i};
        }
        sort(z.begin(), z.end());
        int full = M / x;
        int rest = M % x;
        long ss = 0;
        vector<bool> tk(n);
        for (int i = n - full; i < n; i++) {
            ss += z[i].first;
            tk[z[i].second] = true;
        }
        bool ok = false;
        for (int i = 0; i < n; i++) {
            long sss;
            if (!tk[i]) {
                sss = ss + max(
                        rest * l[i],
                        rest * r[i] - (r[i] - l[i]) * b[i]);
            } else {
                sss = ss - (x * r[i] - (r[i] - l[i]) * b[i]) +
                        (x * r[n - full] - (r[n - full] - l[n - full]) * b[n - full])
                        + max(
                        rest * l[i],
                        rest * r[i] - (r[i] - l[i]) * b[i]);
            }
            if (sss >= s) {
                ok = true;
            }
        }
        if (ok) {
            R = M;
        } else {
            L = M;
        }
    }
    cout << R;

    return 0;
}