Problem:


Score : 400 points

Problem Statement

A university student, Takahashi, has to take N examinations and pass all of them.
Currently, his readiness for the i-th examination is A_{i}, and according to his investigation, it is known that he needs readiness of at least B_{i} in order to pass the i-th examination.

Takahashi thinks that he may not be able to pass all the examinations, and he has decided to ask a magician, Aoki, to change the readiness for as few examinations as possible so that he can pass all of them, while not changing the total readiness.

For Takahashi, find the minimum possible number of indices i such that A_i and C_i are different, for a sequence C_1, C_2, ..., C_{N} that satisfies the following conditions:

The sum of the sequence A_1, A_2, ..., A_{N} and the sum of the sequence C_1, C_2, ..., C_{N} are equal.

For every i, B_i \leq C_i holds.

If such a sequence C_1, C_2, ..., C_{N} cannot be constructed, print -1.

Constraints

1 \leq N \leq 10^5

1 \leq A_i \leq 10^9

1 \leq B_i \leq 10^9

A_i and B_i are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_{N}
B_1 B_2 ... B_{N}

Output

Print the minimum possible number of indices i such that A_i and C_i are different, for a sequence C_1, C_2, ..., C_{N} that satisfies the conditions.
If such a sequence C_1, C_2, ..., C_{N} cannot be constructed, print -1.

Sample Input 1

3
2 3 5
3 4 1

Sample Output 1

3

(A_1, A_2, A_3) = (2, 3, 5) and (B_1, B_2, B_3) = (3, 4, 1). If nothing is done, he cannot pass the first and second exams.
The minimum possible number of indices i such that A_i and C_i are different, 3, is achieved when:

(C_1, C_2, C_3) = (3, 5, 2)

Sample Input 2

3
2 3 3
2 2 1

Sample Output 2

0

In this case, he has to do nothing in order to pass all the exams.

Sample Input 3

3
17 7 1
25 6 14

Sample Output 3

-1

In this case, no matter what is done, he cannot pass all the exams.

Sample Input 4

12
757232153 372327760 440075441 195848680 354974235 458054863 463477172 740174259 615762794 632963102 529866931 64991604
74164189 98239366 465611891 362739947 147060907 118867039 63189252 78303147 501410831 110823640 122948912 572905212

Sample Output 4

5



Sample input:
3
2 3 5
3 4 1


Sample output:
3

Submission status: Accepted

Solution code:
def main():
  n = int(input())
  a = input_list()
  b = input_list()
  c = [a[i] - b[i] for i in range(n)]
  s = sum(c)
  if s < 0:
    print(-1)
    exit(0)
  c.sort()
  ans = 0
  for i in range(n):
    if c[i] < 0:
      pass
    elif c[i] <= s:
      ans += 1
      s -= c[i]
    else:
      break
  print(n-ans)
    
  
def input_list():
  return list(map(int, input().split()))

def input_list_str():
  return map(str, input().split())

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

# 2で割り切れる回数
def divide_two(arg):
  c = 0
  while True:
    if c >= 2:
      break
    if arg % 2 != 0:
      break
    arg //= 2
    c += 1
  return c

# 素因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

import math
import fractions
import collections
from functools import reduce
main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

D = [0] * N
for i in range(N):
  D[i] = A[i] - B[i]
  
if sum(D) < 0:
  print(-1)
  exit(0)

D.sort()
  
minsum = 0
minidx, maxidx = 0, 0
cumsumR = [0] * (N+1)

for i in range(N):
  if D[i] >= 0:
    minidx = i
    break
  minsum += D[i]
  
for j in range(N-1,-1,-1):
  if minsum >= 0:
    maxidx = j
    break
  minsum += D[j]
  
print(N - (maxidx - minidx + 1))

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
a = LIST()
b = LIST()
if sum(a) < sum(b):
    print(-1)
    exit()
dif = [0 for _ in range(n)]
for i in range(n):
    dif[i] = b[i] - a[i]
dif.sort(reverse=True)
cnt = 0
s = 0
for i in range(n):
    if dif[i] > 0:
        cnt += 1
        s += dif[i]
t = 0
for i in reversed(range(n)):
    if t >= s:
        break
    if dif[i] < 0:
        t -= dif[i]
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from bisect import bisect_left


def main():
    length = int(input())
    now_rate = list(map(int, input().split()))
    target_rate = list(map(int, input().split()))
    difference = [0] * length
    for i in range(length):
        difference[i] = now_rate[i] - target_rate[i]
    difference.sort()
    zero_index = bisect_left(difference, 0)
    answer = zero_index
    if zero_index > 0:
        has_prepared = difference[zero_index:]
        not_yet = sum(difference[:zero_index])
        for i in range(-1, -len(has_prepared) - 1, -1):
            not_yet += has_prepared[i]
            if not_yet >= 0:
                answer += abs(i)
                break
        else:
            answer = -1
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
al=list(map(int,input().split()))
bl=list(map(int,input().split()))
pl=[]
nl=0
ans=0
su=0
for a,b in zip(al,bl):
    su+=a-b
    if a>=b:
        pl.append(a-b) 
    else:nl+=a-b;ans+=1
if su<0:print(-1);exit()
pl.sort()


while nl<0:
    nl+=pl.pop()
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
# import bisect
# from collections import Counter, defaultdict, deque, namedtuple
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n = int(input())
    a = list(map(int,ipti().split()))
    b = list(map(int,ipti().split()))

    a_sum = sum(a)
    b_sum = sum(b)

    if a_sum < b_sum:
        print(-1)
        sys.exit()

    a_minus_b = [a[i] - b[i] for i in range(n)]

    a_minus_b.sort()
    minus_count = 0
    minus_sum = 0

    for i in range(n):
        if a_minus_b[i] < 0:
            minus_count += 1
            minus_sum += -(a_minus_b[i])
        else:
            break

    plus_count = 0
    plus_sum = 0

    for i in range(n-1, -1, -1):
        plus_sum += a_minus_b[i]
        plus_count += 1
        if plus_sum >= minus_sum:
            break

    if minus_count == 0:
        print(0)
    else:
        print(plus_count+minus_count)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

ll = [[i - j, i, j] for i, j in zip(a, b)]

ll.sort(reverse=True)
start = n -1

if sum(a) < sum(b):
    print(-1)
    exit(0)

for i in range(n):
    while ll[i][0] > 0:
        if ll[start][0] < 0:
            if ll[i][0] + ll[start][0] >= 0:
                ll[i][0] += ll[start][0]
                ll[start][0] = 0
                start -= 1
            elif ll[i][0] + ll[start][0] < 0:
                ll[start][0] += ll[i][0]
                ll[i][0] = 0
                break
        else:
            break

cnt = 0

for l in ll:
    if l[1] - l[2] != l[0]:
        cnt += 1

print(cnt)
"""
方針
- b - aが小さい要素を使って、b - aが大きい要素を埋めていく
- 

"""

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7



n = I()
A = LI()
B = LI()
rem = []
ret = 0
ans = 0
for i in range(n):
    if B[i] > A[i]:
        ret += B[i] - A[i]
        ans += 1
    elif B[i] < A[i]:
        rem += [A[i] - B[i]]



rem.sort()
if sum(rem) < ret:
    print(-1)
    exit()


while ret > 0:
    ret -= rem.pop()
    ans += 1


print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    c = [a[i] - b[i] for i in range(n)]
    c.sort()
    ans = 0
    x = 0
    for v in c:
        if v < 0:
            ans += 1
            x -= v
    y = 0
    for v in reversed(c):
        if y >= x:
            break
        if v > 0:
            ans += 1
            y += v
    if y >= x:
        print(ans)
    else:
        print("-1")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# A.sort()
# B.sort()

if sum(A) < sum(B):
    print(-1)
else:
    # 方針
    # 不足している準備度を計算
    # 余っている準備度を大きなものから順に奪っていく

    T = []
    for i in range(N):
        T.append([A[i], B[i], A[i]-B[i]])

    T.sort(key=lambda x: x[2])

    if T[0][2] >= 0:
        print(0)
    else:
        fusoku = 0
        cnt = 0

        for ti in T:
            if ti[2] < 0:
                cnt += 1
                fusoku += abs(ti[2])

        T.sort(reverse=True, key=lambda x:x[2])
        for ti in T:
            fusoku -= ti[2]
            cnt += 1
            if fusoku <= 0:
                break

        print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
f=0
mi=0
pr=[]
for i in range(n):
  if a[i]-b[i]<0:
    mi+=(b[i]-a[i])
    f+=1
  else:
    pr.append(a[i]-b[i])
if f==0:
  print(0)
  exit()
if sum(pr)<mi:
  print(-1)
  exit()
pr.sort(reverse=True)
p=0
for i in range(len(pr)):
  p+=pr[i]
  f+=1
  if p>=mi:
    break
print(f)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A = list(map(int, input().split(' ')))
B = list(map(int, input().split(' ')))

if sum(A) < sum(B):
    print(-1)
    exit()

positives = []
sum_negative = 0
num_negative = 0
for a, b in zip(A, B):
    if a > b:
        positives.append(a - b)

    elif a < b:
        sum_negative += b - a
        num_negative += 1


positives.sort(reverse=True)

num_positives = len(positives)
while positives and sum_negative > 0:
    p = positives.pop(0)
    sum_negative -= p

print(num_positives - len(positives) + num_negative)

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
import numpy as np
A=np.array(A)
B=np.array(B)

if np.sum(A)<np.sum(B):
    print(-1)
    exit()

difAB=A-B
negdif=difAB[difAB<0]
posdif=sorted(difAB[difAB>0], reverse=True)
ans=len(negdif)
needs=sum(negdif)
i=0
while needs<0:
    needs+=posdif[i]
    ans+=1
    i+=1

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
pD=[]
mD=[]
for i in range(N):
  d=A[i]-B[i]
  if d>=0:
    pD.append(d)
  else:
    d*=(-1)
    mD.append(d)
if sum(A)<sum(B):
  print(-1)
  exit()
if len(mD)==0:
  print(0)
  exit()
pD=sorted(pD)[::-1]
a=sum(mD)
import numpy
X=numpy.cumsum(pD)
x=0
for i in range(len(pD)):
  if X[i]>=a:
    x=(i+1)
    print(len(mD)+x)
    exit()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
dif = [A[i] - B[i] for i in range(N)]
if sum(A) < sum(B):
  print(-1)
else:
  dif.sort()
  if dif[0] >= 0:
    print(0)
  else:
    p, n = N - 1, 0
    while dif[n] < 0:
      n += 1
    ms = sum(-dif[i] for i in range(n))
    S = dif[p]
    num = n + 1
    while S < ms:
      p -= 1
      S += dif[p]
      num += 1
    print(num)

Submission status: Accepted

Solution code:
import sys
n = int(input())
a_ls = [int(i) for i in sys.stdin.readline().split()]
b_ls = [int(i) for i in sys.stdin.readline().split()]
plus_ls = []
minus_ls = []
for a, b in zip(a_ls, b_ls):
    if b > a:
        minus_ls.append(b - a)
    elif a > b:
        plus_ls.append(a - b)
    else:
        pass
plus_ls.sort(reverse=True)
sum_min = sum(minus_ls)

cnt = len(minus_ls)
for i in plus_ls:
    if sum_min <= 0:
        break
    sum_min -= i
    cnt += 1
if sum_min > 0:
    print(-1)
else:
    print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
if sum(a)<sum(b):
    print(-1)
    exit()
dif_posi=[]
dif_nega=0
cnt=0
for x,y in zip(a,b):
    if x-y<0:
        dif_nega+=x-y
        cnt+=1
    else:
        dif_posi.append(x-y)

dif_posi=sorted(dif_posi,reverse=True)
for i in dif_posi:
    if dif_nega >= 0:
        break
    dif_nega+=i
    cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
if sum(a) < sum(b):
  print(-1)
  exit()
cnt = 0
ans = 0
d = []
for i in range(n):
  if a[i] < b[i]:
    ans += 1
    cnt += b[i] - a[i]
  else:
    d.append(a[i] - b[i])
if ans == 0:
  print(ans)
  exit()
d.sort(reverse=True)
for x in d:
  ans += 1
  cnt -= x
  if cnt <= 0:
    print(ans)
    break

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

sum_a = sum(A)
sum_b = sum(B)
if sum_a < sum_b:
    # impossible
    print(-1)
    exit()

ans = 0
lack = 0
remains = []
for i in range(N):
    a = A[i]
    b = B[i]
    if a < b:
        ans += 1
        lack += b - a
    elif a > b:
        remains.append(a - b)

if ans == 0:
    # no need to change
    print(ans)
    exit()

remains.sort(reverse=True)

count = 0
while lack > 0:
    lack -= remains[count]
    count += 1

print(ans + count)

Submission status: Accepted

Solution code:
from itertools import accumulate
N=int(input())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
AS=sum(A)
BS=sum(B)
if BS>AS:
    print(-1)
elif all(a>=b for a,b in zip(A,B)):
    print(0)
else:
    cap=sum(max(0,b-a) for a,b in zip(A,B))
    M=sum(b-a>0 for a,b in zip(A,B))
    C=sorted((a-b for a,b in zip(A,B)),reverse=True)
    D=list(accumulate(C))
    for i, d in enumerate(D,1):
        if cap<=d:
            print(i+M)
            break

Submission status: Accepted

Solution code:
from itertools import accumulate

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))

if sum(a)<sum(b):
 print(-1)
 exit()

c=[]
lack=0
cnt=0
for i,j in zip(a,b):
  t=i-j
  if i-j>=0:
    c.append(t)
  else:
    lack+=abs(t)
    cnt+=1

if cnt==0:
  print(0)
  exit()

c=sorted(c,reverse=True)
ru=list(accumulate(c))
for i in range(len(ru)):
  if ru[i]>=lack:
    cnt+=i+1
    break

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = [0]*n
for i in range(n):
    C[i] = A[i] - B[i]
C.sort(reverse=True)

if sum(C) < 0:
    print(-1)
else:
    minus = 0
    minus_num = 0
    cnt = 0
    for i in range(n)[::-1]:
        if C[i] < 0:
            minus += C[i]*(-1)
            minus_num += 1
        else:
            break
    while minus > 0:
        minus -= C[cnt]
        cnt += 1
    print(minus_num+cnt)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

c = []
m = 0
ans = 0
for i in range(n):
    if a[i] < b[i]:
        m += b[i] - a[i]
        ans += 1
    elif a[i] > b[i]:
        c.append(a[i] - b[i])

if m == 0:
    print(0)
    exit()

c.sort(reverse = True)
# print(m, c)
tol = 0
for i in range(len(c)):
    tol += c[i]
    ans += 1
    if m <= tol:
        print(ans)
        break
else:
    print(-1)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

if sum(B) > sum(A):
    print(-1)
else:
    C = []
    for i, j in zip(A, B):
        C.append(i-j)
    C.sort()
    
    cnt = 0
    s = 0
    for i in C:
        if i < 0:
            cnt += 1
            s += i
        else:
            break
    if s == 0:
        print(0)
    else:
        for i in C[::-1]:
            s += i
            cnt += 1
            if s >= 0:
                print(cnt)
                break

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
if sum(a)<sum(b):
    print(-1)
    exit()
a=sorted([a[i]-b[i] for i in range(n)])
cnt=0
a.append(0)
k=n
for i in range(n):
    if a[i]<0:
        cnt+=1
        while True:
            if a[k]+a[i]<0:
                a[i]+=a[k]
                k-=1
                cnt+=1
            else:
                a[k]+=a[i]
                break
    else:
        break
print(cnt)

Submission status: Accepted

Solution code:
def examA():
    N = LI()
    N.sort()
    if N==[1,4,7,9]:
        print("YES")
    else:
        print("NO")
    return

def examB():
    S = SI()
    K = "keyence"
    for i in range(7):
        if S[:i]+S[-7+i:]==K:
            print("YES")
            return
    if S[:7]==K:
        print("YES")
        return
    print("NO")
    return

def examC():
    N = I()
    A = LI()
    B = LI()
    if sum(A)<sum(B):
        print(-1)
        return
    dis = [A[i]-B[i] for i in range(N)]
    dis.sort()
#    print(dis)
    cur = 0
    ans = bisect.bisect_left(dis,0)
    need = -sum(dis[:bisect.bisect_left(dis,0)])
    for i in range(N):
        if need<=cur:
            break
        cur += dis[-i-1]
        ans += 1
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

"""

"""

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

d = []
ans = 0
x = 0
for i, v in enumerate(a):
    d.append(b[i] - v)
    if d[i] > 0:
        x += d[i]
        ans += 1

d.sort()
if sum(d) > 0:
    print(-1)
    exit()
else:
    for v in d:
        if x <= 0:
            break
        x += v
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
import bisect
N = int(input())
A= list(map(int,input().split()))
B= list(map(int,input().split()))
diff = [i-j for i,j in zip(B,A)]
p = [i for i in diff if i > 0]
m = sorted([-i for i in diff if i < 0],reverse=1)
msum = list(accumulate(m))
if sum(A) < sum(B):
    print(-1)
elif not p:
    print(0)
else:
    count = len(p)
    rem = sum(p)
    count += bisect.bisect_left(msum,rem)+1
    print(count)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
l=[]
m=[]
ans=0
for x,y in zip(a,b):
    if x-y>=0:
        l+=[x-y]
    else:
        m+=[x-y]
        ans+=1

if ans==0:
    print(0)
    exit()
l=sorted(l,reverse=True)
msum=sum(m)
if sum(m)+sum(l)<0:
    print(-1)
    exit()

for i in l:
    msum+=i
    ans+=1
    if msum>=0:
        print(ans)
        exit()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    less = sum(A) - sum(B)
    if less < 0:
        return print(-1)
    D = [a - b for a, b in zip(A, B)]
    D.sort()
    ans = 0
    cur_sum = 0
    for d in D:
        if d < 0:
            ans += 1
            cur_sum += d
        else:
            break
    for d in D[::-1]:
        if cur_sum >= 0:
            break
        ans += 1
        cur_sum += d
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
D=[]
p=0
s=0
q=0
r=0
for i in range(N):
  D.append(A[i]-B[i])
D.sort(reverse=True)
#print(D)
for i in range(N):
  if D[i]<0:
    s=s+1
    p=p+D[i]
for i in range(N):
  if D[i]>0 and D[i]+r>=abs(p):
    r=r+D[i]
    q=q+1
    break
  else:
    if D[i]>0:
      r=r+D[i]
      q=q+1
    else:
      break
#print("s,p,r",s,p,r,r+p)
if s==0:
  print(0)
else:
  if r<abs(p):
    print(-1)
  else:
    print(s+q)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = []
cnt = 0
if sum(a) < sum(b):
    print(-1)
    exit()
diff = []
for i in range(n):
    diff.append(a[i] - b[i])
diff.sort()
stack = 0
stackcnt = 0
for i in range(n):
    # print(i, stack, diff[i])
    if diff[i] >= 0:
        continue
    if stack < -diff[i]:
        cnt += 1
        stackcnt += 1
        stack += diff[-stackcnt]
        a[-stackcnt] = b[i]
    cnt += 1
    stack -= -diff[i]
    a[i] += -diff[i]
print(cnt)

Submission status: Accepted

Solution code:
from math import fabs
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
tarinai = []
amari = []
for i in range(n):
    if a[i] - b[i] < 0:
        tarinai.append(a[i] - b[i])
    elif a[i] - b[i] > 0:
        amari.append(a[i] - b[i])
tarinai.sort()
amari.sort()
amari.reverse()

ans = 0
if fabs(sum(tarinai)) > sum(amari):
    print('-1')
else:
    ans += len(tarinai)
    val = fabs(sum(tarinai))
    for i in range(n+1):
        #print(val)
        if val <= 0:
            break
        val -= amari[i]
        ans += 1

    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

if sum(a) < sum(b): print(-1)
else:
    d = [j - i for i, j in zip(a, b)]
    d.sort()
    p = 0
    cnt = 0
    for i in d:
        if i > 0: 
            p += i
            cnt += 1
    idx = 0
    while p > 0:
        p += d[idx]
        idx += 1
        cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

if sum(a) < sum(b):
    print("-1")
    exit()
yobun_sum = []

for i in range(N):
    if a[i] > b[i]:
        yobun_sum.append(a[i]-b[i])

yobun_sum.sort()
yobun_sum.reverse()
yobun_cum_sum=[]
cum_sum=0
for i in yobun_sum:
    cum_sum+=i
    yobun_cum_sum.append(cum_sum)

lack_num=0
lack_sum=0

for i in range(N):
    if a[i] < b[i]:
        lack_num+=1
        lack = abs(a[i] - b[i])
        lack_sum+=lack

for i in range(len(yobun_cum_sum)):
    if yobun_cum_sum[i] >= lack_sum:
        break

if lack_sum==0:
    print(0)
else:
    print(lack_num+i+1)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import accumulate
import bisect

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))
b = list(map(int,stdin.readline().rstrip().split()))

pra = []
mai = 0
kosuu = 0
atari = 0

for i in range(n):
    if a[i]-b[i] < 0:
        mai += b[i]-a[i]
        kosuu += 1
        continue
    elif a[i]-b[i] > 0:
        pra.append(a[i]-b[i])
    atari += 1

if sum(pra) < mai:
    print(-1)
    exit()
if atari == n:
    print(0)
    exit()
pra.sort(reverse=True)

pra = list(accumulate(pra))
print(bisect.bisect(pra,mai)+kosuu+1)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split(' ')))
B=list(map(int,input().split(' ')))
plus=[]
minus = 0
ans = 0
if sum(A)<sum(B):
    print(-1)
    exit()
for a,b in zip(A,B):
    if a-b >=0:
        plus.append(a-b)
    elif a-b<0:
        minus += a-b
        ans += 1
if minus==0:
    print(0)
    exit()
for i in sorted(plus,reverse=True):
    minus += i
    ans += 1
    if minus >=0:
        print(ans)
        break

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
Alist = np.array(list(map(int, input().split())), dtype=np.int64)
Blist = np.array(list(map(int, input().split())), dtype=np.int64)
sbn = Alist - Blist
sei = sbn[sbn > 0]
hu = sbn[sbn < 0]

if sum(sei) < abs(sum(hu)):
    print(-1)
elif len(hu) == 0:
    print(0)
else:
    sei = np.sort(sei)[::-1].cumsum()
    print(len(hu) + np.argmax(sei >= abs(sum(hu))) + 1)

Submission status: Accepted

Solution code:
import numpy as np
from sys import exit
N = int(input())
Alist = np.array(list(map(int, input().split())), dtype=np.int64)
Blist = np.array(list(map(int, input().split())), dtype=np.int64)
sbn = Alist - Blist

if sum(sbn) <= 0:
    print(-1)
    exit()

hu = sbn[sbn < 0]
if len(hu) == 0:
    print(0)
    exit()
ans = len(hu)
cost = sum(hu)

sei = np.sort(sbn[sbn > 0])[::-1].cumsum()
# print(cost)
# print(sei)
ind = np.argmax(sei >= abs(cost))
print(ans + ind + 1)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
short=0
ans=0
li=[]
if sum(a)<sum(b):
  print(-1)
  exit()
for i in range(n):
    if a[i]>b[i]:
        li.append(a[i]-b[i])
    elif a[i]<b[i]:
        short+=b[i]-a[i]
        ans+=1
li.sort(reverse=True)
i=0
while short>0:
    short-=li[i]
    i+=1
print(ans+i)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    A = map(int, input().split())
    B = map(int, input().split())

    sum = 0
    ans = 0
    rest = []
    for a, b in zip(A, B):
        if b > a:
            sum += b - a
            ans += 1
        else:
            rest.append(a - b)
    rest.sort(reverse=True)

    if sum <= 0:
        print(0)
        exit()

    for r in rest:
        sum -= r
        ans += 1
        if sum <= 0:
            break
    if sum > 0:
        print(-1)
    else:
        print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
diff = [0]*N
for i in range(N):
  diff[i] = A[i]-B[i]
diff = sorted(diff)
s = 0
cnt = 0
for i in range(N):
  if diff[i] < 0:
    s += abs(diff[i])
    diff[i] = 0
    cnt += 1
  else:
    break
if s == 0:
  print(0)
  exit()
for d in reversed(diff):
  if d > 0 and d >= s:
    cnt += 1
    s = 0
    break
  elif d > 0 and d < s:
    cnt += 1
    s -= d
  elif d <= 0:
    break
if s == 0:
  print(cnt)
else:
  print(-1)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    b = LI()
    if sum(a) < sum(b):
        print(-1)
        return
    c = [a[i]-b[i] for i in range(n)]
    mc = [-i for i in c if i < 0]
    pc = [i for i in c if i >= 0]
    pc.sort(reverse = True)
    for i in range(1,len(pc)):
        pc[i] += pc[i-1]
    s = sum(mc)
    if s == 0:
        print(0)
        return
    for i in range(len(pc)):
        if pc[i] >= s:
            break
    print(len(mc)+i+1)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

diff = [A[i] - B[i] for i in range(N)]
if sum(diff) < 0:
    print(-1)
    exit(0)

minus = [diff[i] for i in range(N) if diff[i] < 0]
plus = [diff[i] for i in range(N) if diff[i] > 0]
plus.sort(reverse=True)
ans = len(minus)
minus_s = sum(minus)*(-1)
id = 0
while(minus_s > 0):
    minus_s -= plus[id]
    id += 1
print(ans+id)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
if sum(A) < sum(B):
    print(-1)
    quit()
C = []
c = 0
for i in range(N):
    if A[i] < B[i]:
        c += B[i] - A[i]
    else:
        C.append(A[i] - B[i])
C.sort()
while c > 0:
    x = C.pop()
    c -= x
print(N-len(C))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from bisect import insort_left

def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    
    if sum(A) < sum(B):
        print(-1)
        exit()

    ok = []
    ng_cnt = 0
    ng_num = 0
    for i in range(N):
        if A[i] - B[i] >= 0:
            ok.append(A[i] - B[i])
        else:
            ng_cnt += 1
            ng_num += B[i] - A[i]
    ok.sort()

    ans = ng_cnt

    while ng_num > 0:
        ans += 1
        ng_num -= ok.pop()

    print(ans)

if __name__ == "__main__":
    main()