Workout plan (Codeforces 1219D)
Tags: Greedy, data structures

Alan decided to get in shape for the summer, so he created a precise workout plan to follow. His plan is to go to a different gym every day during the next N days and lift $$$X[i]$$$ grams on day $$$i$$$. In order to improve his workout performance at the gym, he can buy exactly one pre-workout drink at the gym he is currently in and it will improve his performance by $$$A$$$ grams permanently and immediately. In different gyms these pre-workout drinks can cost different amounts $$$C[i]$$$ because of the taste and the gym's location but its permanent workout gains are the same. Before the first day of starting his workout plan, Alan knows he can lift a maximum of $$$K$$$ grams. Help Alan spend a minimum total amount of money in order to reach his workout plan. If there is no way for him to complete his workout plan successfully output $$$-1$$$.

Input: The first one contains two integer numbers, integers $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ and $$$K$$$ $$$(1 \leq K \leq 10^5)$$$ – representing number of days in the workout plan and how many grams he can lift before starting his workout plan respectively. The second line contains $$$N$$$ integer numbers $$$X[i]$$$ $$$(1 \leq X[i] \leq 10^9)$$$ separated by a single space representing how many grams Alan wants to lift on day $$$i$$$. The third line contains one integer number $$$A$$$ $$$(1 \leq A \leq 10^9)$$$ representing permanent performance gains from a single drink. The last line contains $$$N$$$ integer numbers $$$C[i]$$$ $$$(1 \leq C[i] \leq 10^9)$$$ , representing cost of performance booster drink in the gym he visits on day $$$i$$$.

Output: One integer number representing minimal money spent to finish his workout plan. If he cannot finish his workout plan, output -1.

Note: First example: After buying drinks on days 2 and 4 Alan can finish his workout plan. Second example: Alan cannot lift 40000 grams on day 2.

Sample Inputs:
5 10000
10000 30000 30000 40000 20000
20000
5 2 8 3 6

5 10000
10000 40000 30000 30000 20000
10000
5 2 8 3 6

Sample Outputs:
5

-1

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import heapq as Q
ii = lambda : int(input())
kk = lambda : map(int, input().split())
ll = lambda : list(kk())
(n, k) = kk()
(ls, c, cs) = (kk(), ii(), kk())
cost = 0
pq = []
for v in ls:
    Q.heappush(pq, cs.__next__())
    while v > k and pq:
        k += c
        cost += Q.heappop(pq)
    if v > k:
        print(-1)
        exit()
print(cost)

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import heapq
(n, k) = map(int, input().split())
vals = list(map(int, input().split()))
gain = int(input())
cost = list(map(int, input().split()))
heap = []
heapq.heapify(heap)
ans = 0
broke = False
for s in range(n):
    heapq.heappush(heap, cost[s])
    if k >= vals[s]:
        continue
    else:
        while len(heap) > 0 and k < vals[s]:
            k += gain
            ans += heapq.heappop(heap)
        if k < vals[s]:
            broke = True
            break
if broke == False:
    print(ans)
else:
    print(-1)

Solution (Python):
from math import *
from sys import *
from heapq import *
from collections import defaultdict
import os, sys
from io import IOBase, BytesIO
M = 10 ** 9 + 7

def pow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res *= a
        a *= a
        b >>= 1
    return res

def powmod(a, b, m):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % m
        a *= a
        b >>= 1
    return res

def inv(a, m):
    return powmod(a, m - 2, m)

def alldivisors(n):
    list = []
    arr = []
    for i in range(1, int(sqrt(n) + 1)):
        if n % i == 0:
            if n / i == i:
                arr += [i]
            else:
                arr += [i]
                list.append(n // i)
    arr += list[::-1]
    return arr

def primefactorisation(n):
    potentional_p = 3
    itog_list = defaultdict(int)
    if n % 2 == 0:
        itog_list[2] = 0
    while n % 2 == 0:
        n = n // 2
        itog_list[2] += 1
    while n - 1:
        if potentional_p > n ** 0.5:
            itog_list[n] += 1
            return itog_list
        while n % potentional_p == 0:
            n = n // potentional_p
            itog_list[potentional_p] += 1
        potentional_p += 2
    return itog_list

def main():
    (n, k) = list(map(int, input().split()))
    arr = list(map(int, input().split()))
    a = int(input())
    c = list(map(int, input().split()))
    res = 0
    temp = []
    heapify(temp)
    for i in range(n):
        heappush(temp, c[i])
        if arr[i] > k:
            while len(temp) > 0 and k < arr[i]:
                k += a
                res += temp[0]
                heappop(temp)
            if k < arr[i]:
                print(-1)
                return
    print(res)
BUFSIZE = 8192

class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = 'x' in file.mode or 'w' in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill():
            pass
        return super(FastIO, self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill()
            self.newlines = s.count(b'\n') + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            (self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()