Участник:Tenzo(savok)/Bakery

Материал из DISCOPAL
Перейти к: навигация, поиск

Суть такова - сначала мы сортируем наши пары (доставка, цена) по доставке, и берем m - 1 самых дорогих по цене с помощью кучи. Потом просто добираем один элемент с dev_cost + cost, чтобы у нас сумма максимальна была. Решение вроде O(n log n), поэтому все хорошо сработало.

https://www.codechef.com/problems/BAKCOST

import heapq
 
t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    cost = list(map(int, input().split()))
    dev_cost = list(map(int, input().split()))
    data = []
 
    for i in range(n):
        data.append([dev_cost[i], cost[i]])
 
    data.sort(key=lambda x: x[0])
    ans = 0
    psum = [0] * (n + 1)
    pq = []
    heapq.heapify(pq)
    sum = 0
    for i in range(n - 1, 0, -1):
        if i >= (n - (m - 1)):
            sum += data[i][1]
            psum[i] = sum
            heapq.heappush(pq, data[i][1])
        else:
            heapq.heappush(pq, data[i][1])
            sum += data[i][1]
            sum -= heapq.heappop(pq)
            psum[i] = sum
    for i in range(n):
        if i + m - 1 < n:
            ans = max(ans, data[i][0] * m + (psum[i + 1] + data[i][1]))
    print(ans)