Microtransactions (easy version) (Codeforces 1165F1)
Tags: Greedy, binary search

The only difference between easy and hard versions is constraints.Ivan plays a computer game that contains some microtransactions to make characters look cooler. Since Ivan wants his character to be really cool, he wants to use some of these microtransactions — and he won't start playing until he gets all of them.Each day (during the morning) Ivan earns exactly one burle.There are $$$n$$$ types of microtransactions in the game. Each microtransaction costs $$$2$$$ burles usually and $$$1$$$ burle if it is on sale. Ivan has to order exactly $$$k_i$$$ microtransactions of the $$$i$$$-th type (he orders microtransactions during the evening).Ivan can order any (possibly zero) number of microtransactions of any types during any day (of course, if he has enough money to do it). If the microtransaction he wants to order is on sale then he can buy it for $$$1$$$ burle and otherwise he can buy it for $$$2$$$ burles.There are also $$$m$$$ special offers in the game shop. The $$$j$$$-th offer $$$(d_j, t_j)$$$ means that microtransactions of the $$$t_j$$$-th type are on sale during the $$$d_j$$$-th day.Ivan wants to order all microtransactions as soon as possible. Your task is to calculate the minimum day when he can buy all microtransactions he want and actually start playing.

Input: The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 1000$$$) — the number of types of microtransactions and the number of special offers in the game shop.The second line of the input contains $$$n$$$ integers $$$k_1, k_2, \dots, k_n$$$ ($$$0 \le k_i \le 1000$$$), where $$$k_i$$$ is the number of copies of microtransaction of the $$$i$$$-th type Ivan has to order. It is guaranteed that sum of all $$$k_i$$$ is not less than $$$1$$$ and not greater than $$$1000$$$.The next $$$m$$$ lines contain special offers. The $$$j$$$-th of these lines contains the $$$j$$$-th special offer. It is given as a pair of integers $$$(d_j, t_j)$$$ ($$$1 \le d_j \le 1000, 1 \le t_j \le n$$$) and means that microtransactions of the $$$t_j$$$-th type are on sale during the $$$d_j$$$-th day.

Output: Print one integer — the minimum day when Ivan can order all microtransactions he wants and actually start playing.


Sample Inputs:
5 6
1 2 0 2 0
2 4
3 3
1 5
1 2
1 5
2 3

5 3
4 2 1 3 2
3 5
4 2
2 5

Sample Outputs:
8

20

Solution (Python):
from collections import defaultdict
import sys
(n, m) = map(int, input().split())
trans = [0] + list(map(int, input().split()))
offers = [list(map(int, input().split())) for _ in range(m)]
offers.sort()

def canDo(num1):
    lastOs = dict()
    for x in offers:
        if x[0] > num1:
            break
        lastOs[x[1]] = x[0]
    lastD = defaultdict(lambda : [])
    for x in lastOs:
        lastD[lastOs[x]].append(x)
    transC = trans.copy()
    burles = 0
    for i in range(1, num1 + 1):
        burles += 1
        if len(lastD[i]) != 0:
            for x in lastD[i]:
                temp = min(burles, transC[x])
                transC[x] -= temp
                burles -= temp
    return burles >= sum(transC) * 2
sum1 = sum(trans)
left = sum1 - 1
right = sum1 * 2
while left != right:
    mid = (left + right) // 2
    if canDo(mid):
        right = mid
    else:
        left = mid + 1
print(left)

Solution (Python):
def binary_search():
    left = 1
    right = 2000
    while left < right:
        mid = (left + right) // 2
        if check(mid):
            right = mid
        else:
            left = mid + 1
    return left

def check(mid):
    t = [0] * (n + 1)
    for (day, typ) in b:
        if day > mid:
            break
        t[typ] = day
    d = [0] * (mid + 1)
    for i in range(1, n + 1):
        d[t[i]] += a[i - 1]
    m = 0
    for i in range(1, mid + 1):
        m += 1
        if m >= d[i]:
            m -= d[i]
            d[i] = 0
        else:
            d[i] -= m
            m = 0
    return m >= 2 * sum(d)
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in range(m):
    b.append(list(map(int, input().split())))
b.sort()
print(binary_search())

Solution (Python):
(n, m) = input().split()
n = int(n)
m = int(m)
nList = input().split()
bList = [0] * len(nList)
for i in range(len(nList)):
    nList[i] = int(nList[i])
shopD = {}
shopT = {}
oHis = []
mHis = []
maxD = 0
for i in range(m):
    (d, t) = input().split()
    if nList[int(t) - 1] != 0:
        maxD = max(maxD, int(d))
        if d not in shopD.keys():
            shopD.update({d: [int(t)]})
        elif int(t) not in shopD[d]:
            shopD[d].append(int(t))
        if t not in shopT.keys():
            shopT.update({t: [int(d)]})
        elif int(d) not in shopT[t]:
            shopT[t].append(int(d))
for (i, j) in shopT.items():
    j = list(dict.fromkeys(j))
    j.sort()
    shopT[i] = j
for (i, j) in shopD.items():
    j = list(dict.fromkeys(j))
    shopD[i] = j
total = sum(nList)
coin = 0
day = 0

def modifyMis(t, left):
    if left == 0:
        for ii in range(len(mHis))[::-1]:
            if mHis[ii]['t'] == t:
                mHis.pop(ii)
    else:
        for ii in range(len(mHis))[::-1]:
            if mHis[ii]['t'] == t:
                mHis[ii]['n'] = left
while total > 0 and day < maxD:
    coin += 1
    day += 1
    oHis.append({'t': [], 'n': []})
    if str(day) in shopD.keys():
        for t in shopD[str(day)]:
            if nList[t - 1] > 0:
                if bList[t - 1] > 0 and shopT[str(t)][0] != day and (coin > nList[t - 1] - bList[t - 1]) and (len(mHis) > 0) and (coin > 0):
                    i = 0
                    j = 0
                    while shopT[str(t)][i] < day:
                        extraC = 0
                        d = shopT[str(t)][i]
                        if t in oHis[d - 1]['t']:
                            indexT = oHis[d - 1]['t'].index(t)
                            extraC += oHis[d - 1]['n'][indexT]
                            bList[t - 1] -= oHis[d - 1]['n'][indexT]
                            total += oHis[d - 1]['n'][indexT]
                            oHis[d - 1]['t'].pop(indexT)
                            oHis[d - 1]['n'].pop(indexT)
                        while j < len(mHis) and mHis[j]['d'] < d:
                            j += 1
                        while extraC > 0 and len(mHis) > j:
                            thisT = mHis[j]['t']
                            thisD = mHis[j]['d']
                            change = min(extraC, mHis[j]['n'])
                            bList[thisT - 1] += change
                            total -= change
                            extraC -= change
                            mHis[j]['n'] -= change
                            modifyMis(thisT, nList[thisT - 1] - bList[thisT - 1])
                            if thisT in oHis[thisD - 1]['t']:
                                oHis[thisD - 1]['n'][oHis[thisD - 1]['t'].index(thisT)] += change
                            else:
                                oHis[thisD - 1]['t'].append(thisT)
                                oHis[thisD - 1]['n'].append(change)
                        i += 1
                        coin += extraC
            buy = min(nList[t - 1] - bList[t - 1], coin)
            if buy != 0:
                oHis[day - 1]['t'].append(t)
                oHis[day - 1]['n'].append(buy)
                total -= buy
                bList[t - 1] += buy
                modifyMis(t, nList[t - 1] - bList[t - 1])
                coin -= buy
            if nList[t - 1] - bList[t - 1] > 0:
                mHis.append({'d': day, 't': t, 'n': nList[t - 1] - bList[t - 1]})
    if coin >= total * 2:
        break
day += max(total * 2 - coin, 0)
print(day)