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:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
D = sorted(a - b for a, b in zip(A, B))

def f():
    i, j = 0, len(D) - 1
    p = 0
    ans = 0
    #print(D)
    while j >= i:
        # print(i, j, D[i], D[j], p)
        if D[i] >= 0:
            return ans
        if p >= -D[i]:
            p += D[i]
            i += 1
            ans += 1
            continue
        p += D[j]
        j -= 1
        ans += 1
    if p >= 0:
        return ans
    return -1

print(f())

Submission status: Accepted

Solution code:
N = int(input())
a_list = tuple(map(int, input().split()))
b_list = tuple(map(int, input().split()))
a_sum = sum(a_list)
b_sum = sum(b_list)

if b_sum > a_sum:
    print(-1)
    exit()

minus = {}
plus = {}
for i in range(N):
    a = a_list[i]
    b = b_list[i]
    tmp = a - b
    if tmp < 0:
        if tmp in minus:
            minus[tmp] += 1
        else:
            minus[tmp] = 1
    else:
        if tmp in plus:
            plus[tmp] += 1
        else:
            plus[tmp] = 1

minus = sorted(minus.items(), key= lambda x:x[0])
plus = sorted(plus.items(), key= lambda x:-x[0])
ans = 0
changed = 0
for k, v in minus:
    ans += v
    changed += (k * v)
if changed <0:
    for k, v in plus:
        for j in range(1, v+1):
            ans += 1
            changed += k
            if changed >= 0:
                print(ans)
                exit()
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)
elif all([a >= b for (a,b) in zip(A,B)]):
    print(0)
else:
    D = sorted([a-b for (a,b) in zip(A,B)])
    Negative = [d for d in D if d < 0]
    negative_sum = sum(Negative)
    positive_sum = 0
    count = 0
    for d in reversed(D):
        count += 1
        positive_sum += d
        if positive_sum > - negative_sum:
            break
    print(count + len(Negative))

Submission status: Accepted

Solution code:
N=int(input())

A=list(map(int,input().split()))
B=list(map(int,input().split()))



plusdiff=[]
minusdiff=[]
diffcount=0
Asum=0
Bsum=0

for i in range(N):
  Asum+=A[i]
  Bsum+=B[i]
  if A[i]-B[i]>0:
    plusdiff.append(A[i]-B[i])
  elif A[i]-B[i]<0:
  	minusdiff.append(abs(A[i]-B[i]))


if len(minusdiff)==0:
  print(0)
  exit()

if Asum<Bsum:
  print(-1)
  exit()

plusdiff.sort(reverse=True)
minusdiff.sort(reverse=True)
  
#print(plusdiff,minusdiff)

answer=0
flag=2
while(len(minusdiff)!=0):
  answer+=flag
  if plusdiff[0]>minusdiff[0]:
    plusdiff[0]=plusdiff[0]-minusdiff[0]
    flag=1
    minusdiff.pop(0)
  elif plusdiff[0]==minusdiff[0]:
    plusdiff.pop(0)
    minusdiff.pop(0)
    flag=2
  else:
    minusdiff[0]=minusdiff[0]-plusdiff[0]
    plusdiff.pop(0)
  
    
print(answer)

Submission status: Accepted

Solution code:
n = input()
arr = map(int,raw_input().split())
brr = map(int,raw_input().split())
drr = []
for i in range(n):
	drr.append(arr[i]-brr[i])
drr.sort()
ans = 0
negsum = 0
for i in range(n):
	if drr[i] >= 0:
		break
	else:
		negsum += abs(drr[i])
		ans += 1
drr = drr[::-1]
possum = 0
for i in range(n):
	if drr[i] <= 0:
		break
	else:
		if possum >= negsum:
			break
		else:
			possum += drr[i]
			ans += 1
if possum >= negsum:
	print ans
else:
	print "-1"

Submission status: Accepted

Solution code:
import sys
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
l = []
sumA = sum(A)
sumB = sum(B)

tmp = 0
cnt = 0
if sumA < sumB:
    print("-1")
    sys.exit()
else:
    for i in range(N):
        if A[i] >= B[i]:
            l.append(A[i]-B[i])
        else:
            tmp += A[i]-B[i]
            cnt += 1
l.sort(reverse=True)

j = 0
while tmp < 0:
    tmp += l[j]
    cnt += 1
    j += 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()
d = [A[i]-B[i] for i in range(N)]
d.sort()
neg = 0
count = 0
for e in d:
    if e < 0:
        neg += e
        count += 1
        continue
    break
for e in d[::-1]:
    if neg >= 0:
        break
    neg += e 
    count += 1
print(count)

Submission status: Accepted

Solution code:
import bisect
def 解():
    N = int(input())
    aA=[int(_) for _ in input().split()]
    aB=[int(_) for _ in input().split()]
    aD =[aA[i]-aB[i] for i in range(N)]

    if sum(aD) < 0:
        print(-1)
        exit()
    else:
        aD.sort()
        i0 = bisect.bisect_left(aD,0)
        if i0 == 0:
            print(0)
        elif i0 == N-1 :
            print(N)
        else:
            iM = sum(aD[:i0])
            for i in range(N-1,i0 - 1 ,-1):
                iM += aD[i]
                if iM > 0:
                    print(i0 + (N - i))
                    exit()
解()

Submission status: Accepted

Solution code:
import numpy as np

def judge(A, B):
    sum_A, sum_B = sum(A), sum(B)
    if sum_A < sum_B:
        return -1
    D = np.sort(np.array(A) - np.array(B))
    num = 0
    pid = D.argmax()
    nid = len(D[D < 0]) - 1
    pnew, nnew = True, True
    while nid >= 0:
        if D[pid] + D[nid] > 0:
            num += pnew + nnew
            D[pid] += D[nid]
            D[nid] = 0
            nid -= 1
            pnew, nnew = False, True
        elif D[pid] + D[nid] == 0:
            num += pnew + nnew
            D[pid] = 0
            D[nid] = 0
            pid -= 1
            nid -= 1
            pnew, nnew = True, True
        else:
            num += pnew + nnew
            D[nid] += D[pid]
            D[pid] = 0
            pid -= 1
            pnew, nnew = True, False
    return num

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
print(judge(A, B))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
d=[]
for i in range(n):
    d.append(a[i]-b[i])
d.sort()
count=0
if sum(d)<0:
    print(-1)
    quit()
e=0
f=0
for i in d:
    if i<0:
        e+=i
        count+=1
while e<0:
    e+=d[-1]
    d.pop(-1)
    count+=1
print(count)

Submission status: Accepted

Solution code:
def main():
    """
    1 <= N <= 10^5
    1 <= Ai,Bi <= 10^9
    """
    N = int(input())
    *A, = map(int, input().split())
    *B, = map(int, input().split())

    ans = f(N, A, B)
    print(ans)


def a(N, A, B):
    ans = 0
    return ans


def f(N, A, B):
    diff = [b - a for a, b in zip(A, B)]
    diff = sorted(diff)
    diff_sum = sum(diff)

    if diff_sum > 0:
        return -1

    if len([d for d in diff if d <= 0]) == N:
        return 0

    start = 0
    end = N - 1
    used = [False] * N
    while start < end:
        ds = diff[start]
        de = diff[end]
        if ds <= 0 and de <= 0:
            break

        if ds < 0 and de > 0:
            cost = min(abs(ds), de)
            diff[start] += cost
            diff[end] -= cost

            used[start] = True
            used[end] = True

        if diff[start] >= 0:
            start += 1
        if diff[end] <= 0:
            end -= 1

    ans = sum(used)
    return ans


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = list(map(int,input().split())) #準備度
B = list(map(int,input().split())) #試験

A = np.array(A)
B = np.array(B)


sumA = sum(A)
sumB = sum(B)

if sumA < sumB:
    print(-1)
else:
    gap = A - B
    minus = gap[gap<0]
    numminus = len(gap[gap<0])
    if numminus == 0:
        print(0)
    else:
        needs = - minus.sum()
        sortgap = np.sort(gap)[::-1]
        s = 0
        for i in range(N):
            s += sortgap[i]
            if s >= needs:
                changedplus = i+1
                break
        print(changedplus + numminus)

Submission status: Accepted

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


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

    diff.sort()

    minus = sum([d for d in diff if d < 0])
    result = len([d for d in diff if d < 0])

    for d in diff[::-1]:
        if minus >= 0:
            break
        minus += d
        result += 1

    return(result)

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import numpy as np

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

c=[]
for i in range(n):
    c.append(a[i] - b[i])

c.sort(reverse=True)
d=np.array(c)
z=np.sum(d < 0)

x=np.sum(d[ d < 0])
y=np.sum(d[ d > 0])

if x == 0:
    print("0")
    exit()

if x + y < 0:
    print("-1")
    exit()    

for i,num in enumerate(c):
    x += num
    if x >= 0:
        print(z+i+1)
        exit()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
diff = [0 for _ in range(N)]
for i in range(N):
    diff[i] = A[i] - B[i]
diff = sorted(diff)
diff_copy = diff.copy()

i = 0
j = N-1

flag = True
while True:
    if diff[i]<0:
        while True:
            if i>=N or j<0 or i==j:
                flag = False
                break

            if abs(diff[i])>diff[j]:
                diff[i] += diff[j]
                diff[j] = 0
                j -= 1
            else:
                diff[j]-=abs(diff[i])
                diff[i] = 0
                break
        i += 1
    else:
        break



if flag:
    ans = 0
    for i in range(N):
        if diff_copy[i]!=diff[i]:
            ans += 1
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(m) for m in input().split()]
b = [int(m) for m in input().split()]
difp = []
difm = []
difmmm = []
difr = []
for i in range(n):
    if a[i] - b[i] >= 0:
        difp.append([a[i] - b[i], i])
    else:
        difm.append([a[i] - b[i], i])
        difmmm.append(1)
        difr.append(abs(a[i] - b[i]))

difp.sort(reverse=True)

if sum(a) < sum(b):
    print(-1)
    exit()
Q = sum(difmmm)
R = sum(difr)
tmp = 0
sign = Q
if difm == []:
    print(0)
    exit()
for i in range(len(difp)):
    tmp += difp[i][0]
    if tmp >= R:
        sign += i + 1
        break

print(sign)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
dis1 = []
dis2 = []
num = 0
ans = 0
tmp = 0

for i in range(N):
    num = A[i] - B[i]
    if num > 0:
        dis1.append(num)
    elif num < 0:
        dis2.append(num)

if sum(A) < sum(B):
    ans = -1
elif len(dis2) == 0:
    ans = 0
else:
    dis1.sort(reverse = True)
    num = sum(dis2)
    ans += len(dis2)
    for i in range(len(dis1)):
        num += dis1[i]
        ans += 1
        if num >= 0:
            break

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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


a = np.array(a)
b = np.array(b)


if np.sum(a) < np.sum(b):
    ans = -1
else:

    diff = a - b
    diff = np.sort(diff)
    if np.sum(diff<0) == 0:
        ans = 0
    else:
        for ind in range(len(diff)):
            if diff[ind] > 0:
                break

        minus = np.sum(diff[:ind])
        minus_num = ind

        yoyuu = diff[ind:][::-1]

        for ind in range(len(yoyuu)):
            minus += yoyuu[ind]
            if minus > 0:
                ans = minus_num + ind + 1
                break
            if minus == 0:
                ans = minus_num + ind
                break

print(ans)

Submission status: Accepted

Solution code:
# n = 12
n = int(input())
# a = [757232153, 372327760, 440075441, 195848680, 354974235, 458054863, 463477172, 740174259, 615762794, 632963102, 529866931, 64991604]
a = [int(i) for i in input().split()]
# b = [74164189, 98239366, 465611891, 362739947, 147060907, 118867039, 63189252, 78303147, 501410831, 110823640, 122948912, 572905212]
b = [int(i) for i in input().split()]
c = [0 for _ in range(n)]
for i in range(n):
    c[i] = a[i] - b[i]
if sum(c) < 0:
    print(-1)
    exit()
c.sort()
count = 0
minus = 0
for i in range(n):
    if c[i] < 0:
        minus += c[i]
        count += 1
    else:
        break
for i in reversed(range(n)):
    if minus < 0:
        minus += c[i]
        count += 1
    else:
        print(count)
        exit()

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()

q = []
p = []
d = 0

for i in range(n):
    if a[i] - b[i] < 0:
        q.append(a[i]-b[i])
    elif a[i] - b[i] > 0:
        p.append(a[i]-b[i])
    else:
        d += 1

s = sum(q)
p = sorted(p)
while s < 0:
    if p == []:
        print(-1)
        exit()
    else:
        t = p.pop()
        s += t

print(n - d - len(p))

Submission status: Accepted

Solution code:
#問題C
import numpy as np
N = int(input())
A = list(map(int,input().split())) #準備度
B = list(map(int,input().split())) #試験

A = np.array(A)
B = np.array(B)


sumA = sum(A)
sumB = sum(B)

if sumA < sumB:
    print(-1)
else:
    gap = A - B
    minus = gap[gap<0]
    numminus = len(gap[gap<0])
    if numminus == 0:
        print(0)
    else:
        needs = - minus.sum()
        sortgap = np.sort(gap)[::-1]
        s = 0
        for i in range(N):
            s += sortgap[i]
            if s >= needs:
                changedplus = i+1
                break
        print(changedplus + numminus)

Submission status: Accepted

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

a_sum = 0
b_sum = 0
diff = list()
for i in range(n):
  a_sum += int(a[i])
  b_sum += int(b[i])
  diff.append(int(a[i])-int(b[i]))

if a_sum < b_sum:
  print(-1)
else:
  diff.sort()

  minus = 0
  for i in range(n):
    if diff[i] < 0:
      minus += diff[i]
    else:
      change1 = i
      break

  plus = 0
  for i in range(n-1, -1, -1):
    plus += diff[i]
    if plus >= -minus:
      change2 = n-i
      break
  
  if minus == 0:
    change2 = 0
  
  print(change1 + change2)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]

diff = [0] * N
minus_count = 0
minus_sum = 0
for i in range(N):
    diff[i] = A[i] - B[i]
    if diff[i] < 0:
        minus_count += 1
        minus_sum += -diff[i]

diff = sorted(diff, reverse=True)
cumsum = [0] * (N + 1)
for i in range(N):
    cumsum[i] += diff[i] + cumsum[i - 1]

# print(minus_count)
# print(minus_sum)
# print(diff)
# print(cumsum)


def check(x):
    a = x - minus_count
    if a < 0:
        return False

    plus_sum = cumsum[a - 1]
    # print(x, a)
    # print('plus', plus_sum)
    # print('minus', minus_sum)
    if plus_sum >= minus_sum:
        return True


def main():
    if sum(A) < sum(B):
        print(-1)
        return

    sup = N
    inf = -1
    while sup - inf > 1:
        mid = (sup + inf) // 2

        if check(mid):
            sup = mid
        else:
            inf = mid

    print(sup)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

dic = []
S = [0,0]
minus = [0,0]
for i in range(N):
    a = int(A[i])
    b = int(B[i])
    S[0]+=a
    S[1]+=b
    k = a-b
    if k >= 0:
        dic.append(k)
    else:
        minus[0]+=1#回数
        minus[1]+=k#値
if S[0] < S[1]:
    print(-1)
    exit()

lis = sorted(dic,reverse=True)

n=0
while minus[1]<0:
    minus[0]+=1
    minus[1]+=lis[n]
    n+=1


print(minus[0])
    # if a < b:
    #     break
    # if i == N-1:
    #     print(0)
    #     exit()
# if sum(A) < sum(B):
#     print(-1)

#差を調べる、辞書 A<Bの数を調べる

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())), np.int64)
B = np.array(list(map(int, input().split())), np.int64)
if sum(B) > sum(A):
    print(-1)
else:
    diff = A - B
    sort_idx = diff.argsort()
    # A = A[sort_idx]
    # B = B[sort_idx]
    diff = diff[sort_idx]
    l = 0
    r = N-1
    ans = sum(diff < 0)
    if ans != 0:
        ans += 1
    while True:
        if diff[l] >= 0:
            break
        if diff[r] >= -diff[l]:
            diff[r] += diff[l]
            diff[l] = 0
            l += 1
        else:
            diff[l] += diff[r]
            diff[r] = 0
            r -= 1
            ans += 1
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
import numpy as np
a = np.zeros(n, dtype=int)
b = np.zeros(n, dtype=int)
buf1  = input().split()
buf2  = input().split()
for i in range(n):
	a[i] = int(buf1[i])
	b[i] = int(buf2[i])
r = 0
if(np.sum(a) < np.sum(b)):
	r = -1
else:
	c = a - b
	c = np.sort(c)
	if(c[0] >= 0):
		r = 0
	else:
		ii = -1
		for i in range(n):
			if(c[i] >= 0):
				ii = i
				break
		debt = np.sum(c[:i])
		for i in range(n):
			debt += c[n-1-i]
			if(debt >= 0):
				r = ii+(i+1)
				break
print(r)

Submission status: Accepted

Solution code:
import math
import copy




def nCast(number):
    if type(number)==str:
        return int(number)
    for idx in range(0,len(number)):
        if type(number[idx])==str:

            number[idx]=int(number[idx])
        else:
            nCast(number[idx])
    return number
    
def inputArr(w):
    l=list()
    for idx in range(0,w):
        l.append(input())
    return l
def inputArr1(w):
    l=list()
    for idx in range(0,w):
        l.append(input())
    return l

n=nCast(input())
a=nCast(input().split())
b=nCast(input().split())
c=list()
def func():
    result=0
    if sum(a)<sum(b):
        return -1
    for idx in range(0,len(a)):
        c.append(a[idx]-b[idx])
    c.sort()
    need=0
    result=0

    for number in c:
        if number<0:
            need+=number
            result+=1
        else:
            break

    if need==0:
        return 0
    for number in reversed(c):
        result+=1
        need+=number
        if need>=0:
            break
    return result

print(func())

Submission status: Accepted

Solution code:
# coding: utf-8

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

    if sum(A) < sum(B):
        return -1

    diff_sum = 0
    diff_cnt = 0
    diff_list = [0] * N
    for i in range(N):
        diff_list[i] = A[i] - B[i]
        if A[i] < B[i]:
            diff_sum += B[i] - A[i]
            diff_cnt += 1

    diff_list_sorted = sorted(diff_list, reverse=True)

    use_sum = 0
    for i in range(N):
        if use_sum >= diff_sum:
            break
        use_sum += diff_list_sorted[i]
        diff_cnt += 1

    return diff_cnt


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    As = list(map(int, input().split()))
    sumA = sum(As)
    Bs = list(map(int, input().split()))
    sumB = sum(Bs)

    if sumB > sumA:
        print(-1)
        return

    pos = []
    neg = []
    for i in range(n):
        diff = As[i] - Bs[i]

        if diff > 0:
            pos.append(diff)
        elif diff < 0:
            neg.append(diff)

    pos.sort(reverse=True)
    sum_neg = sum(neg)

    work_neg = sum_neg
    i = 0
    while work_neg < 0:
        work_neg += pos[i]
        i += 1

    ans = len(neg) + i
    print(ans)

    return

main()

Submission status: Accepted

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

D = [0 for i in range(N)]
for i in range(N):
    D[i] = A[i] - B[i]
    if D[i] < 0:
        tarinai += -1 * D[i]
    elif D[i] > 0:
        amari += D[i]
if amari < tarinai:
    print(-1)
else:
    D = sorted(D)
    left = 0
    right = N - 1
    count = 0
    while True:
        if D[left] >= 0:
            break
        if D[right] == -1 * D[left]:
            left += 1
            right -= 1
            count += 2
        elif D[right] > - 1 * D[left]:
            D[right] -= -1 * D[left]
            left += 1
            count += 1
            if D[left] >= 0:
                count += 1
        else:
            D[left] += D[right]
            right -= 1
            count += 1
    print(count)

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(0)

C = [A[i] - B[i] for i in range(N)]

has_shortage = False

for i in range(N):
    if C[i] < 0:
        has_shortage = True
        break

if has_shortage is False:
    print(0)
    exit(0)

C = sorted(C, reverse=True)
i = 0
j = N-1
ans = 2
while C[j] < 0:
    if -C[j] > C[i]:
        C[j] += C[i]
        C[i] = 0
        i += 1
        ans += 1
        continue
    else:
        C[i] += C[j]
        # C[j] = 0
        j -= 1
        ans += 1
        continue

ans -= 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

short_sum = 0
exceed_diffs = []
count = 0

for i in range(0, N):
    diff = A[i] - B[i]
    if diff < 0:
        short_sum += -diff
        count += 1
    elif diff > 0:
        exceed_diffs.append(diff)

exceed_diffs.sort(reverse = True)

for diff in exceed_diffs:
    if short_sum <= 0:
        break

    short_sum -= diff
    count += 1

if short_sum > 0:
    print(-1)
else:
    print(count)

Submission status: Accepted

Solution code:
n = int(input())
Ascore = list(map(int,input().split()))
Bscore = list(map(int,input().split()))
count = 0
positive = []
nsum = 0
if sum(Ascore) < sum(Bscore):
    print(-1)
else:
    for a,b in zip(Ascore,Bscore):
        tmp = a-b
        if tmp < 0:
            count += 1
            nsum += tmp
        else:
            positive.append(tmp)
    positive = sorted(positive)[::-1]
    while(nsum<0):
        p = positive.pop(0)
        count += 1
        nsum += p
    print(count)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

nn = []
n = []
for a, b in zip(A, B):
    d = a - b
    if d == 0:
        continue
    if d > 0:
        nn.append(d)
    else:
        n.append(-d)

ans = len(n)

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

s = sum(n)

if s > sum(nn):
    print(-1)
    exit()

t = 0
for v in sorted(nn, reverse=True):
    t += v
    ans += 1
    if t >= s:
        break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = [A[i] - B[i] for i in range(0,N)]
C.sort()
p = 0
ans = 0
j = len(A) - 1
for i in range(0,N):
  if C[i] < 0:
    p += C[i]
    ans += 1
  else:
    break
  if p < 0:
    if C[j] > 0:
      p += C[j]
      ans += 1
      C[j] = 0
      j -= 1

if sum(A) < sum(B):
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b
import bisect

n = getN()
pres = getlist()
needs = getlist()

mores = []
for i in range(len(pres)):
    mores.append(pres[i] - needs[i])

ans = 0
mores.sort(reverse=False)

div = bisect.bisect_left(mores, 0)

ans += div
husoku = -(sum(mores[:div]))

amari = mores[div:]#.sort(reverse=True)
if type(amari) == int:
    amari = [amari]
amari.sort(reverse=True)

if sum(amari) < husoku:
    ans = -1
else:
    if husoku > 0:
        for a in amari:
            ans += 1
            if a >= husoku:
                break
            else:
                husoku -= a

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=[]
    d=0
    a=0
    for i in range(len(A)):
        c=A[i]-B[i]
        D.append(c)
        if c<0:
            a+=1
            d-=c
    D.sort()
    j=1
    while d>0:
        if d>D[-j]:
            a+=1
            d-=D[-j]
            j+=1
        else:
            a+=1
            break
    print(a)

Submission status: Accepted

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

if sum(An) < sum(Bn):
    print(-1)
    exit()

fusoku = [b-a for a,b in zip(An,Bn) if a < b ]
yojo = [a-b for a, b in zip(An, Bn) if a > b]
yojo.sort(reverse=True)
sum_fusoku = sum(fusoku)
ans = len(fusoku)
sum_score = 0
for y in yojo:
    if sum_score >= sum_fusoku:
        break
    ans += 1
    sum_score += y

# print(sum_score)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
suma,sumb=0,0
l=[0 for _ in range(n)]
for i in range(n):
    suma+=a[i]
    sumb+=b[i]
    l[i]=b[i]-a[i]
if sumb>suma:
    print(-1)
    exit()
l.sort()
cnt=0
ans=0
for i in range(n):
    if l[i]>0:
        cnt+=l[i]
        ans+=1
for i in l:
    if cnt>0:
        cnt+=i
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


N = I()
A = LI()
B = LI()
if sum(A) < sum(B):
    print(-1)
    exit()

cnt = 0
need = 0
mochi = []
for i in range(N):
    a = A[i]
    b = B[i]
    if a < b:
        cnt += 1
        need += b - a
    else:
        mochi.append(a - b)

mochi.sort()
# print(cnt, need)
# print(mochi)

while need > 0:
    p = mochi.pop()
    need -= p
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(x) for x in input().split()]
B=[int(y) for y in input().split()]

ans=0
task=0
power=[]

for i in range(N):
  if A[i]< B[i]:
    ans+=1
    task+=(B[i]-A[i])
  else:
    power.append(A[i]-B[i])

power.sort(reverse=True)
for i in range(len(power)):
  if task<=0:
    break
  else:
    task-=power[i]
    ans+=1

if task>0:
  print(-1)
else:
  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)
    exit(0)

t = 0
m = 0
L = []
for k in range(N):
    if A[k] > B[k]:
        L.append(A[k]-B[k])
    else:
        m += B[k] - A[k]
        t += 1

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

L = (sorted(L))[::-1]
for e in L:
    m -= e
    t += 1
    if m <= 0:
        break
print(t)

Submission status: Accepted

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

given = []
giving = []
for Ai, Bi in zip(A, B):
    if Ai < Bi: given.append(Bi - Ai)
    else: giving.append(Ai - Bi)

cost = sum(given)
if cost < 1:
    print(0)
else:
    ans = len(given)
    giving.sort(key=lambda x: -x)
    for Xi in giving:
        # print('#', Xi)
        ans += 1
        cost -= Xi
        if cost <= 0:
            print(ans)
            break
        else: continue
    else:
        print(-1)

Submission status: Accepted

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

#足りない合計
short=0
arr=[]
count=0
for i,j in zip(A,B):
    if i<j:
        short+=j-i
        count+=1
    else:
        arr.append(i-j)

arr.sort()

if short==0:
    print(0)
else:
    for i in arr[::-1]:
        short-=i
        count+=1
        if short<=0:
            break
    if short>0:
        print(-1)
    else:
        print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jan 13 21:11:51 2019

@author: Yamazaki Kenichi
"""

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

d = [0 for i in range(N)]

a = 0
b = 0
C = [0 for i in range(N)]
ans = 0

for i in range(N):
    if A[i] < B[i]:
        d[i] = 1
        a += A[i]
        b += B[i]
    else:
        C[i] += A[i]-B[i]

C.sort()
c =b-a 

if sum(C) < b-a:
    ans = -1
elif d.count(1) == 0:
    ans =0
else:
    ans = d.count(1)
    i=1
    while c>=0:
       c -= C[-i]
       ans+=1
       i +=1
    
print(ans)

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))
N = int(input())
A = inpl()
B = inpl()
ans = 0

if sum(A) <= sum(B):
    print(-1)
else:
    NG = 0
    OK = []
    for i in range(N):
        if A[i] - B[i] > 0:
            OK.append(A[i] - B[i])
        elif A[i] - B[i] < 0:
            NG += A[i] - B[i]
            ans += 1
    OK = sorted(OK)
    while NG < 0:
        ans += 1
        NG += OK.pop()
    print(ans)