Участник:Penkin.D.A./Friends and Candies

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

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

Рассмотрим массив из Li и Ri. Отсортируем его изначально по Li. Затем проходя по этому массиву максимально раздаем конфеты из левых корзин и определяем кто из друзей уже удовлетворен. Затем делаем аналогично с правыми корзинами.

Решение получает runtime error, но проходит на тестах если запускать со своим вводом этих тестов (custom input)

maxn=1e6+7
 
def Solve():
    n,m=map(int,input().split())
    a = int(maxn)*[0]
    a = map(int, input().split())
    a = list(a)
    p = 0*[m]
    for i in range(m):
        p.append([0]*2)
    for i in range(m):
        p[i] = map(int, input().split())
        p[i] = list(p[i])
    #print(p)
    p.sort()
    #print(p)
    lptr = 0
    assigned = []
    unassigned = []
    for i in range(m):
        while (a[lptr] == 0) and (lptr < p[i][0]):
            lptr += 1
        if (lptr < p[i][0]) and (a[lptr] != 0):
            a[lptr]-=1
            assigned.append(p[i][1])
            assigned.sort()
            continue
        len_assigned = len(assigned) - 1
        if len_assigned != -1:
            if (assigned[len_assigned] <= p[i][1]):
                unassigned.append(p[i][1])
                unassigned.sort()
                continue
        else:
            if (len(assigned) == 0):
                unassigned.append(p[i][1])
                unassigned.sort()
                continue
        unassigned.append(assigned[len_assigned])
        unassigned.sort()
        assigned.pop(len_assigned)
        assigned.append(p[i][1])
        assigned.sort()
    rptr = n - 1
    ans = len(assigned)
    for u in unassigned:
        while(a[rptr] == 0) and ((rptr+u) > n):
            rptr -= 1
        if ((rptr+u) >= n) and (a[rptr] != 0):
            a[rptr] -= 1
            ans += 1
    print(ans)
 
t = int(input())
while (t > 0):
    Solve()
    t-=1