# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1145282 | abdu_ep53 | Topical (NOI23_topical) | C++20 | 0 ms | 0 KiB |
import sys
from collections import deque
def max_modules_completed(n, k, requirements, upgrades):
# Начальные знания по всем темам
knowledge = [0] * k
# Храним модули в виде списка (requirements, upgrades)
modules = [(requirements[i], upgrades[i]) for i in range(n)]
# Фильтруем модули, которые Benson может выполнить сразу
available = deque()
remaining = []
for req, upg in modules:
if all(knowledge[j] >= req[j] for j in range(k)):
available.append((req, upg))
else:
remaining.append((req, upg))
completed = 0
while available:
# Выполняем текущий доступный модуль
req, upg = available.popleft()
# Обновляем знания
for j in range(k):
knowledge[j] += upg[j]
completed += 1
# Проверяем, какие модули теперь стали доступными
new_remaining = []
for req, upg in remaining:
if all(knowledge[j] >= req[j] for j in range(k)):
available.append((req, upg))
else:
new_remaining.append((req, upg))
remaining = new_remaining
return completed
# Читаем входные данные
n, k = map(int, sys.stdin.readline().split())
requirements = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
upgrades = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
# Вычисляем и выводим результат
print(max_modules_completed(n, k, requirements, upgrades))