Cleaning the Phone (Codeforces 1475D)
Tags: DP, two pointers

Polycarp often uses his smartphone. He has already installed $$$n$$$ applications on it. Application with number $$$i$$$ takes up $$$a_i$$$ units of memory.Polycarp wants to free at least $$$m$$$ units of memory (by removing some applications).Of course, some applications are more important to Polycarp than others. He came up with the following scoring system — he assigned an integer $$$b_i$$$ to each application:   $$$b_i = 1$$$ — regular application;  $$$b_i = 2$$$ — important application. According to this rating system, his phone has $$$b_1 + b_2 + \ldots + b_n$$$ convenience points.Polycarp believes that if he removes applications with numbers $$$i_1, i_2, \ldots, i_k$$$, then he will free $$$a_{i_1} + a_{i_2} + \ldots + a_{i_k}$$$ units of memory and lose $$$b_{i_1} + b_{i_2} + \ldots + b_{i_k}$$$ convenience points.For example, if $$$n=5$$$, $$$m=7$$$, $$$a=[5, 3, 2, 1, 4]$$$, $$$b=[2, 1, 1, 2, 1]$$$, then Polycarp can uninstall the following application sets (not all options are listed below):   applications with numbers $$$1, 4$$$ and $$$5$$$. In this case, it will free $$$a_1+a_4+a_5=10$$$ units of memory and lose $$$b_1+b_4+b_5=5$$$ convenience points;  applications with numbers $$$1$$$ and $$$3$$$. In this case, it will free $$$a_1+a_3=7$$$ units of memory and lose $$$b_1+b_3=3$$$ convenience points.  applications with numbers $$$2$$$ and $$$5$$$. In this case, it will free $$$a_2+a_5=7$$$ memory units and lose $$$b_2+b_5=2$$$ convenience points. Help Polycarp, choose a set of applications, such that if removing them will free at least $$$m$$$ units of memory and lose the minimum number of convenience points, or indicate that such a set does not exist.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 10^9$$$) — the number of applications on Polycarp's phone and the number of memory units to be freed.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the number of memory units used by applications.The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 2$$$) — the convenience points of each application.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output on a separate line:   -1, if there is no set of applications, removing which will free at least $$$m$$$ units of memory;  the minimum number of convenience points that Polycarp will lose if such a set exists. 

Note: In the first test case, it is optimal to remove applications with numbers $$$2$$$ and $$$5$$$, freeing $$$7$$$ units of memory. $$$b_2+b_5=2$$$.In the second test case, by removing the only application, Polycarp will be able to clear only $$$2$$$ of memory units out of the $$$3$$$ needed.In the third test case, it is optimal to remove applications with numbers $$$1$$$, $$$2$$$, $$$3$$$ and $$$4$$$, freeing $$$10$$$ units of memory. $$$b_1+b_2+b_3+b_4=6$$$.In the fourth test case, it is optimal to remove applications with numbers $$$1$$$, $$$3$$$ and $$$4$$$, freeing $$$12$$$ units of memory. $$$b_1+b_3+b_4=4$$$.In the fifth test case, it is optimal to remove applications with numbers $$$1$$$ and $$$2$$$, freeing $$$5$$$ units of memory. $$$b_1+b_2=3$$$.

Sample Inputs:
5
5 7
5 3 2 1 4
2 1 1 2 1
1 3
2
1
5 10
2 3 2 3 2
1 2 1 2 1
4 10
5 1 3 4
1 2 1 2
4 5
3 2 1 2
2 1 2 1

Sample Outputs:
2
-1
6
4
3

Solution (Python):
import bisect
readline = lambda : map(int, input().split())

def solve():
    (_, m) = readline()
    (one, two) = ([], [])
    for (mem, con) in zip(readline(), readline()):
        if con == 1:
            one.append(mem)
        else:
            two.append(mem)
    one.sort(reverse=True)
    two.sort(reverse=True)
    (pone, ptwo) = ([0], [0])
    for x in one:
        pone.append(pone[-1] + x)
    for x in two:
        ptwo.append(ptwo[-1] + x)
    ans = float('inf')
    for (d1, m1) in enumerate(pone):
        d2 = bisect.bisect_left(ptwo, m - m1)
        if d2 != len(ptwo):
            ans = min(ans, d1 + 2 * d2)
    print(-1 if ans == float('inf') else ans)
_T = 1
_T = int(input())
for _ in range(_T):
    solve()

Solution (Python):
def solve():
    (n, m) = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    (c, d) = ([], [])
    (n1, n2) = (0, 0)
    for i in range(n):
        if b[i] == 1:
            c.append(a[i])
            n1 += 1
        else:
            d.append(a[i])
            n2 += 1
    if sum(a) < m:
        return -1
    c.sort(reverse=True)
    d.sort(reverse=True)
    (sum1, sum2) = ([0] * (n1 + 1), [0] * (n2 + 1))
    for i in range(1, n1 + 1):
        sum1[i] = sum1[i - 1] + c[i - 1]
    for i in range(1, n2 + 1):
        sum2[i] = sum2[i - 1] + d[i - 1]
    res = float('inf')
    for i in range(n2 + 1):
        (now, use) = (sum2[i], i * 2)
        cha = m - now
        if cha <= 0:
            res = min(res, use)
        else:
            if sum1[n1] + now < m:
                continue
            (l, r) = (1, n1)
            while l <= r:
                mid = (l + r) // 2
                if sum1[mid] + now < m:
                    l = mid + 1
                else:
                    r = mid - 1
                    res = min(res, use + mid)
    return res
t = int(input())
for _ in range(t):
    print(solve())

Solution (Python):
from bisect import bisect_left, bisect_right
from math import inf

def main():
    T = int(input())
    for i in range(T):
        v1 = []
        v2 = []
        (n, m) = map(int, input().split())
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
        for i in range(n):
            if b[i] == 1:
                v1.append(a[i])
            else:
                v2.append(a[i])
        v1.sort(reverse=True)
        v2.sort(reverse=True)
        ls1 = []
        ls2 = []
        temp = 0
        for i in v1:
            temp += i
            ls1.append(temp)
        temp = 0
        for i in v2:
            temp += i
            ls2.append(temp)
        ls1.insert(0, 0)
        ls2.insert(0, 0)
        ans = inf
        for i in range(len(ls1)):
            cur = bisect_left(ls2, m - ls1[i])
            if cur >= len(ls2):
                cur -= 1
            if ls1[i] + ls2[cur] >= m:
                ans = min(ans, i + 2 * cur)
                if cur == 0:
                    break
        if ans == inf:
            print(-1)
        else:
            print(ans)
main()