Problem p03019 (python)

Fixed submission:

"""

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

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

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

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

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

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

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

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

"""

from sys import stdin

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

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

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

sblu.sort()
sblu.reverse()

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

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

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

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

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

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

    ans = min(ans,nans)

print (ans)

Buggy submission (verdict: Runtime Error):

"""

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)