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

if sum(a) < sum(b):
    print(-1)
else:
    c = list(a[i]-b[i] for i in range(n))
    c.sort()
    if c[0] >= 0:
        print(0)
    else:
        extra = sum(c)
        cnt = 0
        for i in range(n):
            if c[i] > 0 and c[i] <= extra:
                extra -= c[i]
                cnt += 1
        print(n-cnt)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[]
dif=0
ans=0
if sum(a)<sum(b):
    print(-1)
else:
    for i in range(n):
        x,y=a[i],b[i]
        if x<y:
            dif+=y-x
            ans+=1
        else:
            c.append(x-y)
    c.sort()
    while c and dif>0:
        ans+=1
        dif-=c.pop()
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
Ali = [ int(it) for it in input().split() ]
Bli = [ int(it) for it in input().split() ]

Sli = [ Bli[i] - Ali[i] for i in range(N) ]

if ( sum(Sli)>0 ):
  print (-1)
else:
  po = [ it for it in Sli if it>0 ]
  ng = [ it for it in Sli if it<0 ]
  agr = sum(po)
  ng.sort()
  
  for i in range(1000000):
    if (agr<=0):
      print (len(po)+i)
      break
    agr+=ng[i]

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 = [a-b for a,b in zip(A,B)]
  D.sort()
  
  import bisect
  i = bisect.bisect_left(D,0)
  up = - sum(D[:i])
  
  j=0
  while up>0:
    j += 1
    up -= D[-j]
    
  print(i + j)

Submission status: Accepted

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


surplus = [(a - b) for a, b in zip(A, B) if (a - b) > 0]
surplus.sort(reverse=True)
surplus_acc = [0] + list(accumulate(surplus))

short = [(b - a) for a, b in zip(A, B) if (b - a) > 0]
need = sum(short)
short_num = len(short)


if need > sum(surplus):
    print(-1)
    exit()
else:
    for i in range(len(surplus_acc)):
        if surplus_acc[i] >= need:
            print(i + short_num)
            exit()

Submission status: Accepted

Solution code:
if __name__=="__main__":
    n = int(input())
    A = [int(i) for i in input().split(' ')]
    B = [int(i) for i in input().split(' ')]
    allA = 0
    allB = 0
    for a, b in zip(A, B):
        allA += a
        allB += b
    if (allA < allB):
        print(-1)
        exit(0)
    C = []
    sum = 0
    ans = 0
    for i in range(n):
      if (A[i] < B[i]):
          sum += A[i] - B[i]
          ans += 1
      else:
          C.append(A[i] - B[i])
    if (sum >= 0):
        print(ans)
        exit(0)
    C = sorted(C)
    C.reverse()
    for i in (C):
        sum += i
        ans += 1
        if (sum >= 0):
            print(ans)
            exit(0)

Submission status: Accepted

Solution code:
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)
else:
    x,num,m = [],0,0
    for i in range(n):
        if a[i]<b[i]:
            num+=b[i]-a[i]
            m+=1
        else: x.append(b[i]-a[i])
    x,k = sorted(x),0
    while num>0:
        num+=x[k]
        k+=1
    print(m+k)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [A[i] - B[i] for i in range(N)]

ans = 0
p = 0
q = 0
l = []

for i, c in enumerate(C):
    if c < 0:
        ans += 1
        p += c
    else:
        q += c
        l.append(c)

if p + q < 0:
    print(-1)
    exit()

l.sort()


while p < 0:
    p += l[-1]
    l.pop()
    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:
    cnt = ssum = 0
    d = [a[i]-b[i] for i in range(n)]
    for i in range(n):
        if d[i] < 0:
            cnt += 1
            ssum -= d[i]
    d.sort()
    for i in range(n-1, -1, -1):
        if ssum <= 0:
            break
        ssum -= d[i]
        cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
#キーエンス2019
#C:ExamandWizard
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
if sum(A)<sum(B):
    print(-1)
    exit()
data=[]
need=0
ans=0
for i in range(N):
    if A[i]>B[i]:
        data.append(A[i]-B[i])
    elif A[i]<B[i]:
        need+=B[i]-A[i]
        ans+=1
data.sort()
while need>0:
    ans+=1
    need-=data.pop()
print(ans)
#notsub

Submission status: Accepted

Solution code:
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)
else:
    a = []
    b = []
    for x, y in zip(A, B):
        if x >= y:
            a.append(x-y)
        else:
            b.append(y-x)
    a.sort(reverse=True)
    c = sum(b)
    ans = len(b)
    ind = 0
    while c > 0:
        c = c-a[ind]
        ind += 1
        ans += 1
    print(ans)

Submission status: Accepted

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

diff = []
neg = 0
count = 0

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

for a, b in zip(A, B):
    diff += [a-b]
    if a < b:
        count += 1
        neg += a - b

for d in sorted(diff, reverse=True):
    if neg >= 0:
        break
    count += 1
    neg += d

print(count)

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)

diff = []
neg = 0
count = 0

if sum_B > sum_A:
    print(-1)
    exit()

for a, b in zip(A, B):
    diff += [a-b]
    if a < b:
        count += 1
        neg += a - b

for d in sorted(diff, reverse=True):
    if neg >= 0:
        break
    count += 1
    neg += d

print(count)

Submission status: Accepted

Solution code:
# input
N = int(input())
a_list = [int(i) for i in input().split()]
b_list = [int(i) for i in input().split()]

# const
counter = 0
overed = 0
affs = []
i = 0
# process
for a,b in zip(a_list,b_list):
    if b>a:
        overed += b-a
        counter += 1
    elif b<a:
        affs.append(a-b)
affs = sorted(affs, reverse = True)

while overed>0:
    if i == len(affs):
        print(-1)
        exit()
    overed -= affs[i]
    counter += 1
    i += 1
print(counter)

Submission status: Accepted

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

D=[]
Asum=0
Bsum=0
Dnegative=0
Dnegative_n=0
Dsum=0
for i in range(N):
  D.append(A[i]-B[i])
  Asum += A[i]
  Bsum += B[i]
  if A[i]-B[i]<0:
    Dnegative += A[i]-B[i]
    Dnegative_n += 1
if Asum < Bsum:
  print(-1)
  exit()

if Dnegative_n==0:
  print(0)
  exit()
D.sort()

for i in range(N):
  Dsum -= D[N-i-1]
  if Dsum <= Dnegative:
    print(Dnegative_n+i+1)
    exit()

Submission status: Accepted

Solution code:
#WA
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
diff = [0]*n

neg = 0
cnt = 0
for i in range(n):
    x = a[i]-b[i]
    diff[i] = x
    if x < 0:
        cnt += 1
        neg += x

if sum(diff)<0:
    print(-1)
    exit()

for x in sorted(diff, reverse=True):
    if neg >= 0:
        break
    cnt += 1
    neg += x

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
ov = []
un = 0
cnt = 0
for i in range(n):
  c = a[i]-b[i]
  if c >= 0:
    ov.append(c)
  else:
    un += c
    cnt += 1
if un == 0:
  print(0)
else:
  un *= -1
  ov.sort(reverse=True)
  ov2 = 0
  for i in range(len(ov)):
    ov2 += ov[i]
    if ov2 >= un:
      print(cnt+i+1)
      break
  else:
    print(-1)

Submission status: Accepted

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

mns = []
res = 0
plus = 0
for i in range(n):
    if a[i] < b[i]:
        res += 1
        plus += b[i]-a[i]
    elif a[i] > b[i]:
        mns.append(b[i]-a[i])
mns.sort()
cnt = 0
while plus > 0:
    plus += mns[cnt]
    res += 1
    cnt += 1
    if plus > 0 and cnt == len(mns):
        print(-1)
        exit()
print(res)

Submission status: Accepted

Solution code:
def redistribution(dif,minus,plus):
    while dif[minus] < 0:
        if dif[minus] + dif[plus] >= 0: #一部充当
            dif[plus] = dif[plus] + dif[minus]
            dif[minus] = 0
        else: #全部充当
            dif[minus] = dif[minus] + dif[plus]
            dif[plus] = 0
            plus -= 1
    minus += 1
    return [minus,plus]

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
check = True
for i in range(n):
    if a[i] < b[i]:
        check = False
if sum(b) > sum(a):
    print("-1")
elif check:
    print("0")
else:
    dif = []
    for i in range(n):
        dif.append(a[i]-b[i])
    dif.sort()
    minus = 0
    plus = -1
    while dif[minus] < 0:
        temp = redistribution(dif,minus,plus)
        minus = temp[0]
        plus = temp[1]
    print(abs(plus)+minus)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
SA = sum(A)
SB = sum(B)
if SA < SB:
  print(-1)
else:
  under = []
  over = []
  cnt = 0
  for i in range(N):
    if A[i] < B[i]:
      under.append(abs(A[i]-B[i]))
      cnt += 1
    elif A[i] > B[i]:
      over.append(abs(A[i]-B[i]))
  over.sort()
  over.reverse()
  un_cnt = 0
  ov_cnt = 0
  if len(under) != 0:
    cnt += 1
    while un_cnt < len(under):
      if over[ov_cnt] > under[un_cnt]:
        over[ov_cnt] -= under[un_cnt]
        un_cnt += 1
      else:
        while under[un_cnt] > over[ov_cnt]:
          under[un_cnt] = under[un_cnt]-over[ov_cnt]
          ov_cnt += 1
          cnt += 1
        if under[un_cnt] == over[ov_cnt]:
          un_cnt += 1
          ov_cnt += 1
        else:
          over[ov_cnt] -= under[un_cnt]
          un_cnt += 1
  print(cnt)

Submission status: Accepted

Solution code:
import sys

num_exam = int(raw_input())
current_scores    = map(int, raw_input().split())
exam_boarderlines = map(int, raw_input().split())

margin_scores = []
lack_scores   = []
count_adjusted = 0

if sum(current_scores) < sum(exam_boarderlines):
  print(-1)
  sys.exit()

for i in range(num_exam):
  if current_scores[i] < exam_boarderlines[i]:
    lack_scores.append(current_scores[i] - exam_boarderlines[i])
    count_adjusted += 1
  elif current_scores[i] > exam_boarderlines[i]:
    margin_scores.append(current_scores[i] - exam_boarderlines[i])

desc_sorted_margin_scores = sorted(margin_scores, reverse=True)
total_lack_score = sum(lack_scores)
for i in range(len(desc_sorted_margin_scores)):
  if total_lack_score >= 0:
    break

  total_lack_score += desc_sorted_margin_scores[i]
  count_adjusted += 1

print(count_adjusted)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
s=sum(a)-sum(b)
if s<0:
    print(-1)
else:
    c=[0]*n
    po=0
    ze=0
    ne=0
    nc=0
    for i in range(n):
        c[i]=a[i]-b[i]
        if c[i]>0:
            po+=c[i]
        elif c[i]<0:
            ne-=c[i]
            nc+=1
        else:
            ze+=1
    ans=0
    c=sorted(c)
    for i in range(n-1,-1,-1):
        if ne>0:
            ans+=1
        if c[i]>0:
            ne=ne-c[i]
        
    print(nc+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()]
D=[[A[i]-B[i],i] for i in range(N)]
D.sort()
s=0
for i in range(N):
  if D[i][0]<0:
    s+=D[i][0]
    D[i][0]=0
  elif D[i][0]>=0:
    break
for i in range(N)[::-1]:
  if s+D[i][0]<0:
    s+=D[i][0]
    D[i][0]=0
  else:
    D[i][0]+=s
    s=0
    break
if s!=0:
  print(-1)
  exit()
C=[""]*N
ans=0
for i in range(N):
  C[D[i][1]]=D[i][0]+B[D[i][1]]
  if C[D[i][1]]!=A[D[i][1]]:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = input().split()
B = input().split()
count = 0
a = []
b = []
c = []
e = 0
for i in range(N):
  a.append(float(A[i]))
  b.append(float(B[i]))
su=sum(a)-sum(b)
if su <0:
  print(-1)
  exit()
else:
  for i in range(N):
    C=a[i]-b[i]
    if C >=0:
      c.append(C)
    else:
      e+=C
      count += 1
c.sort(reverse=True)
if e == 0:
  print(0)
  exit()
else:
  for i in range(len(c)):
    e=c[i]+e
    count += 1
    if e >= 0:
      print(count)
      exit()
    else:
      continue

Submission status: Accepted

Solution code:
n = int(input())
ax = list(map(int, input().split()))
bx = list(map(int, input().split()))

if sum(ax) < sum(bx):
    print(-1)
    exit()

ans = 0
plus = []
minus = 0
for a, b, in zip(ax, bx):
    if a > b:
        plus.append(a-b)
    elif a < b:
        minus += b-a
        ans += 1
plus.sort(reverse=True)
for i in plus:
    if minus <= 0:
        break
    minus -= i
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    b = LI()
    t = 0
    k = 0
    d = []
    for i in range(n):
        if a[i] < b[i]:
            t += 1
            k += b[i] - a[i]
        else:
            d.append(b[i]-a[i])
    d.sort()
    for e in d:
        if k <= 0:
            break
        k += e
        t += 1
    if k > 0:
        return -1

    return t



print(main())

Submission status: Accepted

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


# 各テストの余裕を小さい順に
margins = [[i, a - b] for i, (a, b) in enumerate(zip(A, B)) if (a - b) > 0]
margins.sort(key=lambda m: m[1])

# 調整済みA
X = A[:]

# 余裕が大きい方から使っていく
for i in range(N):
    while (A[i] < B[i]) and margins:
        cost = B[i] - A[i]
        mi, margin = margins[-1]

        if margin > cost:
            margins[-1][1] -= cost
            A[mi] -= cost
            A[i] += cost

        else:
            margins.pop()
            A[mi] -= margin
            A[i] += margin


ans = 0
for a, b, x in zip(A, B, X):
    if b - a > 0:
        print(-1)
        break

    if a != x:
        ans += 1
else:
    print(ans)

Submission status: Accepted

Solution code:
def exam_and_wizard(a: list, b: list) -> int:
    if sum(a) < sum(b):
        return -1

    count = 0
    minus = 0
    usable = []
    for _a, _b in zip(a, b):
        if _a < _b:
            minus += _a - _b
            count += 1
        elif _a > _b:
            usable.append(_a - _b)
    
    usable = sorted(usable)
    while minus < 0:
        p = usable.pop()
        minus += p
        count += 1

    
    return count


if __name__ == "__main__":
    # ignore N
    _ = input()
    a = [int(s) for s in input().split()]
    b = [int(s) for s in input().split()]

    ans = exam_and_wizard(a, b)
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [A[i]-B[i] for i in range(N)]
C = sorted(C)
if sum(C) < 0:
  print(-1)
else:
  if C[0] >= 0:
    print(0)
  else :
    cnt = 0
    point = 0
    for i in range(N):
      if C[i] < 0 :
        cnt+=1
        point += C[i]
      else :
        break
    for i in range(N):
      cnt+=1
      point += C[-1-i]
      if point>=0:
        print(cnt)
        break

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


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

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

    ans = 0
    up = []
    sum_shortage = 0
    for i in range(N):
        if A[i] < B[i]:
            sum_shortage += B[i] - A[i]
            ans += 1
        if A[i] > B[i]:
            up.append(A[i] - B[i])

    for val in sorted(up, reverse=True):
        if sum_shortage > 0:
            sum_shortage -= val
            ans += 1
            
        if sum_shortage <= 0:
            break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy
siken_kazu=int(input())
junbido=[int(i) for i in input().split(" ")]
goukakudo=[int(i) for i in input().split(" ")]
yoyudo=[junbido[i]-goukakudo[i] for i in range(siken_kazu)]
counter=0
shakkin=0
tyokin=0
if sum(junbido)<sum(goukakudo):
    counter=-1
else:
    for i in yoyudo:
        if i<0:
            counter+=1
            shakkin-=i
    yoyudo=sorted(yoyudo,reverse=True)
    for i in yoyudo:
        if tyokin>=shakkin:
            break
        else:
            tyokin+=i
            counter+=1
print(counter)

Submission status: Accepted

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

import sys
D,total1,total2,cnt1,cnt2 = [],0,0,0,0
for i in range(N):
    if A[i] == B[i]:
        continue
    elif A[i] > B[i]:
        D.append(A[i]-B[i])
    else:
        total1 += B[i]-A[i]
        cnt1 += 1

D.sort(reverse=True)

if total1==0:
    print(0)
    sys.exit()
else:
    for d in D:
        total2 += d
        cnt2 += 1
        if total2 >= total1:
            print(cnt1+cnt2)
            sys.exit()

print(-1)

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):
        print(-1)
    else:
        c = [a[i] - b[i] for i in range(n)]
        minus = [ci for ci in c if ci < 0]
        plus = sorted([ci for ci in c if ci > 0], reverse=True)
        ans = len(minus)
        total = sum(minus)

        if total != 0:
            for index, p in enumerate(plus, 1):
                total += p
                ans += 1

                if total >= 0:
                    print(ans)
                    exit()
        else:
            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()))
diff = []
if sum(A) < sum(B):
    print(-1)
    exit()
for i in range(N):
    diff.append(A[i] - B[i])

diff = sorted(diff)
i, j = 0, N - 1
num = 0
tmp = 0
while i < N and diff[i] < 0:
    while tmp < abs(diff[i]):
        tmp += diff[j]
        j -= 1
        num += 1
    tmp += diff[i]
    i += 1

print(num + i)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()
B = LIST()

good = []
bad = []
for i in range(N):
    need = A[i] - B[i]
    if need >= 0:
        good.append(need)
    else:
        bad.append(need)

if sum(good) + sum(bad) < 0:
    print(-1)
    exit()

good.sort(reverse=True)

goodsm = 0
badsm = -sum(bad)
cnt = 0
for i in range(len(good)):
    if goodsm >= badsm:
        break
    goodsm += good[i]
    cnt += 1

print(cnt + len(bad))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()
B = LIST()

good = []
bad = []
for i in range(N):
    need = A[i] - B[i]
    if need >= 0:
        good.append(need)
    else:
        bad.append(need)

if sum(good) + sum(bad) < 0:
    print(-1)
    exit()

good.sort(reverse=True)
# このあとの二分探索用に累積和にする
good.insert(0, 0)
for i in range(len(good)-1):
    good[i+1] += good[i]

# badを補填するために必要なgoodの数 + badの総数
print(bisect_left(good, -sum(bad)) + len(bad))

Submission status: Accepted

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

total = 0
diff_list = []
smaller_num = 0
for n in range(N):
    if A[n] < B[n]:
        total += B[n] - A[n]
        smaller_num += 1
    else:
        diff_list.append(A[n] - B[n])

diff_list = sorted(diff_list, reverse = True)
diff_total = 0
diff_count = 0
for i, diff in enumerate(diff_list):
    diff_total += diff
    if diff_total >= total:
        diff_count = i + 1
        break

if smaller_num == 0:
    print(0)
elif diff_total < total:
    print(-1)
else:
    print(smaller_num + diff_count)

Submission status: Accepted

Solution code:
n=int(input())
pre=list(map(int, input().split(" ")))
need=list(map(int, input().split(" ")))
if sum(pre)<sum(need):
  print("-1")
  exit()
difs,difb=0,[]
count=0
for i in range(n):
  if pre[i]<need[i]:
    count+=1
    difs+=need[i]-pre[i]
  elif pre[i]>need[i]:
    difb.append(pre[i]-need[i])
if count==0:
  print(0)
  exit()
difb.sort(reverse=True)
wa=0
for j in difb:
  wa+=j
  count+=1
  if wa>=difs:
    print(count)
    exit()

Submission status: Accepted

Solution code:


s1=input()
s2=map(int,input().split())
s3=map(int,input().split())
originals2=s2


minus=0
count=0
res=[a-b for a,b in zip(s2,s3)]
for r in res:
    if r<0:
        count+=1
        minus+=r
#print(minus)
#print(count)
#print("--")
if minus<0:
    for r in sorted(res,reverse=True):
        minus=minus+r
        count+=1
        if minus>0:
            print(count)
            break
    if minus<0:
        print(-1)
else:
    print(0)

Submission status: Accepted

Solution code:
import copy

in_num = int(input())
in_prepared_list = list(map(int,input().split()))
in_criteria_list = list(map(int,input().split()))

# print(in_num)
# print(in_prepared_list)
# print(in_criteria_list)

# 準備合計より基準合計のほうが大きければ、試験には合格できない
prepared_sum = sum(in_prepared_list)
criteria_sum = sum(in_criteria_list)
diff = prepared_sum - criteria_sum
if diff < 0:
    print('-1')
    exit()

# 準備と基準の差分が大きいものから、不足分に配分していき、
# 合格できるポイントの最終的な配分数を出力する
# print(diff)
# print(in_prepared_list)
# print(in_criteria_list)

diff_list = []
for i in range(in_num):
    diff_list.append(in_prepared_list[i] - in_criteria_list[i])

# print(diff_list)
lower_diff_list = copy.copy(diff_list)
lower_diff_list.sort()
upper_diff_list = copy.copy(diff_list)
upper_diff_list.sort(reverse=True)

# print(lower_diff_list)
# print(upper_diff_list)

if lower_diff_list[0] >= 0:
    print('0')
    exit()

change_count = 0
low_index = 0
upp_index = 0
prev_diff = 0
for i in range(in_num):
    low = lower_diff_list[low_index]
    upp = upper_diff_list[upp_index]
    if low >= 0:
        change_count += 1
        print(change_count)
        exit()
    if prev_diff == 0:
        one_diff = low + upp
    elif prev_diff < 0:
        one_diff = upp + prev_diff
    else:
        one_diff = low + prev_diff

    # print(str(one_diff) + ':' + str(prev_diff))
    prev_diff = one_diff
    if one_diff == 0:
        low_index += 1
        upp_index += 1
        change_count += 2
    elif one_diff < 0:
        upp_index += 1
        change_count += 1
    else:
        low_index += 1
        change_count += 1

# print('error')

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    # diff >= 0 → ノルマ成功
    diff = [a[i] - b[i] for i in range(n)]
    # 調整すべきテスト
    given_score_index = []
    # 調整すべき総点数
    given_score_sum = 0
    # 調整してあげるテスト
    give_score_value = []
    for i in range(n):
        if diff[i] < 0:
            given_score_index.append(i)
            given_score_sum += -diff[i]
        else:
            give_score_value.append(diff[i])
    if not given_score_index:
        print(0)
        return
    if sum(give_score_value) < given_score_sum:
        print(-1)
        return
    # 調整すべきテストは絶対カウント
    ans = len(given_score_index)
    num = 0
    give_score_value.sort(reverse=True)
    for value in give_score_value:
        num += 1
        given_score_sum -= value
        if given_score_sum > 0:
            continue
        break
    ans += num
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def solve(ans, shortage, excess):
    if sum(excess) < shortage:
        return -1
    if ans == 0:
        return 0
    excess.sort(reverse=True)
    tmp = 0
    for i, e in enumerate(excess):
        tmp += e
        if tmp >= shortage:
            return ans + i + 1


n = int(input())
shortage = 0
excess = []
ans = 0
for a, b in zip(map(int, input().split()), map(int, input().split())):
    if a == b:
        continue
    if a > b:
        excess.append(a - b)
    else:
        shortage += b - a
        ans += 1
print(solve(ans, shortage, excess))

Submission status: Accepted

Solution code:
import sys
import io
import numpy as np
import itertools

def parse(inp):
    N=int(next(inp).split()[0])
    A=np.array(next(inp).split(),dtype=int)
    B=np.array(next(inp).split(),dtype=int)
    return N,A,B


def magic(D):
    moved = sum(D < 0)
    if (moved == 0): return 0
    s_minus = sum(D[D < 0])

    pluslist = np.sort(D[D > 0])[::-1]

    for i in itertools.accumulate(pluslist):
        moved += 1
        if (i > abs(s_minus)):
            break

    return moved


def main(inp):
    N = inp[0]
    A = inp[1]
    B = inp[2]
    D = np.empty(N, dtype=int)
    for i in range(N):
        D[i] = A[i] - B[i]

    if (A.sum() < B.sum()):
        return -1
    else:
        return magic(D)


print(main(parse(sys.stdin)))

Submission status: Accepted

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

def solve(N,A,B):
    if sum(A) < sum(B):
        return(-1)
    shortage = 0
    satisfyedSubjetSurpasses = []
    numChangedSubject = 0
    for i in range(N):
        if A[i] < B[i]:
            shortage += B[i] - A[i]
            numChangedSubject += 1
        else:
            satisfyedSubjetSurpasses.append(A[i]-B[i])
    satisfyedSubjetSurpasses.sort(reverse = True)
    index = 0
    while shortage > 0:
        numChangedSubject += 1
        shortage -= satisfyedSubjetSurpasses[index]
        index += 1
    return(numChangedSubject)

print(solve(N,A,B))