백준 #24041 (python)

문제

 

https://www.acmicpc.net/problem/24041

24041번: 성싶당 밀키트

---

Algorithm

i에 대한 모든 S_i의 합이 G 이하이므로 가장 큰 x는 2e9이다. x의 최솟값은 0으로 해서 이진탐색으로 x를 찾는다. x일 이후에도 밀키트를 먹을 수 있으면 최솟값을 증가시키고 없다면 최댓값을 감소시키면서 x를 찾는다.

---

 

 

Code

import sys

input = sys.stdin.readline

N, G, K = map(int, input().split())
kits = []
for i in range(N):
    s, l, o = map(int, input().split())
    kits.append((s, l, o))

left = 0
right = int(2e9)

while True:
    if left > right:
        break
    d = (left + right) // 2
    able = True
    O_1 = []
    O_0 = 0
    for s, l, o in kits:
        germs = s * max(1, d - l)
        if o == 0:
            O_0 += germs
        if O_0 > G:
            able = False
            break
        if o == 1:
            O_1.append(germs)
    if not able:
        right = d - 1
        continue
    able = True
    O_1.sort(reverse = True)
    O_1 = O_1[K :]
    exdate = O_0
    for o in O_1:
        exdate += o
        if exdate > G:
            right = d - 1
            able = False
            break
    if able:
        left = d + 1
print(right)