Problem:


Score : 500 points

Problem Statement

We have a sequence of N integers: A_1, A_2, \cdots, A_N.

You can perform the following operation between 0 and K times (inclusive):

Choose two integers i and j such that i \neq j, each between 1 and N (inclusive). Add 1 to A_i and -1 to A_j, possibly producing a negative element.

Compute the maximum possible positive integer that divides every element of A after the operations. Here a positive integer x divides an integer y if and only if there exists an integer z such that y = xz.

Constraints

2 \leq N \leq 500

1 \leq A_i \leq 10^6

0 \leq K \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \cdots A_{N-1} A_{N}

Output

Print the maximum possible positive integer that divides every element of A after the operations.

Sample Input 1

2 3
8 20

Sample Output 1

7

7 will divide every element of A if, for example, we perform the following operation:

Choose i = 2, j = 1. A becomes (7, 21).

We cannot reach the situation where 8 or greater integer divides every element of A.

Sample Input 2

2 10
3 5

Sample Output 2

8

Consider performing the following five operations:

Choose i = 2, j = 1. A becomes (2, 6).

Choose i = 2, j = 1. A becomes (1, 7).

Choose i = 2, j = 1. A becomes (0, 8).

Choose i = 2, j = 1. A becomes (-1, 9).

Choose i = 1, j = 2. A becomes (0, 8).

Then, 0 = 8 \times 0 and 8 = 8 \times 1, so 8 divides every element of A. We cannot reach the situation where 9 or greater integer divides every element of A.

Sample Input 3

4 5
10 1 2 22

Sample Output 3

7

Sample Input 4

8 7
1 7 5 6 8 2 6 5

Sample Output 4

5



Sample input:
2 3
8 20


Sample output:
7

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque
import itertools
from itertools import permutations
import sys
import bisect
sys.setrecursionlimit(10**6)
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
YNeos='YNeos'
GYN=['Yes','trumpet']
mo=10**9+7
imp='IMPOSSIBLE'

n,k=MI()
a=LI()
s=sum(a)
d=[s]
for i in range(2,int(s**0.5)+1):
    if s%i==0:
        d.append(i)
        if s//i!=i:
            d.append(s//i)
ans=1
for i in d:
    t=0
    if sum([j%i for j in a])%i!=0:
        continue
    else:
        
        x=[j%i if (j%i)<=(i//2) else (j%i)-i for j in a]
        #print(i,a,x)
        x.sort(key=lambda y: -abs(y))
        print(i,x,end='|')
        for j in range(n-1):
            x[-1]+=-x[j]
            t+=abs(x[j])
        if t<=k and x[-1]%i==0:
            ans=max(ans,i)
        print(i,a,x,t)
        #print(i,[j%i for j in a],a,d,sum(a),x)
    


print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N, K = [int(i) for i in input().split()]
a_ls = [int(i) for i in input().split()]

sum_a = sum(a_ls)
cnt = 1
while True:
    if sum_a % cnt == 0:
        target = sum_a / cnt
    else:
        cnt += 1
        continue
    if target == 1:
        break
    new_a_ls = [a % target for a in a_ls]
    small2large = new_a_ls.copy()
    large2small = [target-a for a in new_a_ls]
    heapq.heapify(small2large)
    heapq.heapify(large2small)
    small = heapq.heappop(small2large)
    large = heapq.heappop(large2small)
    new_cnt = 0
    flg = False
    _sum = 0
    while True:
        if small < large:
            large -= small
            small = heapq.heappop(small2large)
            new_cnt += 1
            _sum += small
        elif small == large:
            new_cnt += 2
            _sum += small
            if _sum > K:
                break
            if new_cnt == len(a_ls):
                flg = True
                break
            large = heapq.heappop(large2small)
            small = heapq.heappop(small2large)
        else:
            small -= large
            large = heapq.heappop(large2small)
            new_cnt += 1
            _sum += large
        if len(large2small) == 0 or len(small2large) == 0:
            break
        if _sum > K:
            break
    if flg:
        break
    cnt += 1
print(int(target))

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
AL=list(map(int,input().split()))
summ=0
for i in range(N):
  summ+=AL[i]
candidate=set()
for i in range(1,int(summ**0.5)+1):
  if summ%i==0:
    candidate.add(i)
    candidate.add(summ/i)
ans=0
for x in candidate:
  need=0
  r=[0]*N
  for i in range(N):
    r[i]=AL[i]%x
  sorted(r)
  rsum=0
  for i in range(N):
    rsum=rsum+r[i]
  rindex=int(rsum/x)
  lindex=N-int(rsum/x)
  for i in range(lindex):
    need+=r[i]
  if need<=K:
    ans=max(ans,x)
print(int(ans))

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
AL=list(map(int,input().split()))
summ=0
for i in range(N):
  summ+=AL[i]
candidate=set()
for i in range(1,int(summ**0.5)+1):
  if summ%i==0:
    candidate.add(i)
    candidate.add(summ/i)
ans=0
for x in candidate:
  need=0
  r=[0]*N
  for i in range(N):
    r[i]=AL[i]%x
  sorted(r)
  rsum=0
  lsum=0
  for i in range(N):
    rsum=rsum+r[i]
  rindex=int(rsum/x)
  lindex=N-int(rsum/x)
  for i in range(0,lindex):
    need+=r[i]
  if need<=K:
    ans=max(ans,x)
print(int(ans))

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
AL=list(map(int,input().split()))
summ=0
for i in range(N):
  summ+=AL[i]
candidate=set()
for i in range(1,int(summ**0.5)):
  if summ%i==0:
    candidate.add(i)
    candidate.add(summ/i)
ans=1
for x in candidate:
  need=1e18
  r=[0]*N
  for i in range(N):
    r[i]=AL[i]%x
  sorted(r)
  rsum=0
  lsum=0
  for i in range(N):
    rsum=rsum+x-r[i]
  for i in range(N):
    lsum+=r[i]
    rsum-=x-r[i]
    need=min(need,max(rsum,lsum))
  if need<=K:
    ans=max(ans,x)
print(int(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

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

arr = np.array(a)
wa = sum(arr)
divisors = make_divisors(wa)

ans = 1
for div in divisors:
    cnt = 0
    for i in range(n):
        cnt += min(a[i] % div, div - a[i] % div)
    if cnt % 2 == 0 and cnt / 2 <= k:
        ans = max(ans, div)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

    S = sum(A)
    divisors = make_divisors(S)
    
    for d in divisors:
        R = list(map(lambda x: x % d, A))
        R = [r for r in R if r != 0]
        R.sort()
        
        minus = list(accumulate(R))
        
        plus = list(map(lambda x: d - x, R))
        plus.sort()
        plus = list(accumulate(plus))
        plus.sort(reverse=True)
        
        for i in range(len(R)-1):
            if minus[i] == plus[i+1] and minus[i] <= K:
                print(d)
                exit(0)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

    S = sum(A)
    divisors = make_divisors(S)
    
    for d in divisors:
        R = list(map(lambda x: x % d, A))
        R.sort()

        minus = list(accumulate(R))

        plus = list(map(lambda x: d - x, R))
        plus.sort()
        plus = list(accumulate(plus))
        plus.sort(reverse=True)

        for i in range(N-1):
            if minus[i] == plus[i+1] and minus[i] <= K:
                print(d)
                exit(0)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

    S = sum(A)
    divisors = make_divisors(S)
    
    for d in divisors:
        R = list(map(lambda x: x % d, A))
        R.sort()
        minus = list(accumulate(R))

        R.sort(reverse=True)
        plus = list(accumulate(map(lambda x: d - x, R)))
        plus.sort(reverse=True)

        for i in range(N-1):
            if minus[i] == plus[i+1] and minus[i] <= K:
                print(d)
                exit(0)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

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

candidates = []
sumA = sum(A)

i = 1
while i <= math.sqrt(sumA):
    if sumA % i == 0:
        candidates.append(i)
        candidates.append(int(sumA / i))
    i += 1
    
candidates = sorted(candidates, reverse = True)
end = 0
# candidates loop
for i in range(len(candidates)):
    if end:
        break
    # A loop
    for j in range(len(A)):
        A[j] %= candidates[i]
    A = sorted(A)
    left = sum(A)
    right = 0
    need = max(left, right)
    for l in range(len(A) - 1, -1, -1):
        left -= A[l]
        right += candidates[i] - A[l]
        need = min(need, max(left, right))
    if need <= K:
        print(candidates[i])
        end = 1

Submission status: Wrong Answer

Solution code:
import math

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

candidates = []
sumA = sum(A)

i = 1
while i <= math.sqrt(sum(A)):
    if sumA % i == 0:
        candidates.append(i)
        candidates.append(int(sumA / i))
    i += 1
    
candidates = sorted(candidates, reverse = True)
end = 0
# candidates loop
for i in range(len(candidates)):
    if end:
        break
    # A loop
    for j in range(len(A)):
        A[j] %= candidates[i]
    left = sum(A)
    right = 0
    need = max(left, right)
    for l in range(len(A) - 1, -1, -1):
        left -= A[l]
        right += candidates[i] - A[l]
        need = min(need, max(left, right))
    if need <= K:
        print(candidates[i])
        end = 1

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

    S = sum(A)
    divisors = make_divisors(S)
    
    for d in divisors:
        R = list(map(lambda x: x % d, A))
        R.sort()
        minus = set(accumulate(R))

        R.sort(reverse=True)
        plus = set(accumulate(map(lambda x: d - x, R)))

        a = list(minus & plus)
        for ans in a:
            if ans <= K:
                print(d)
                break

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

    S = sum(A)
    divisors = make_divisors(S)
    
    for d in divisors:
        R = list(map(lambda x: x % d, A))
        R.sort()
        minus = set(accumulate(R))

        R.sort(reverse=True)
        plus = set(accumulate(map(lambda x: d - x, R)))

        a = list(minus & plus)
        if a:
            ans = a[0]
        if ans <= K:
            print(d)
            break

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
S = input()

S = list(map(int, S.split()))

N = S[0]
K = S[1]

A = list(map(int, input().split()))
A_sum = sum(A)
A_max = max(A)

divisor = []

for i in range(1, A_sum+1, 1):
    if (A_sum % i == 0):
        divisor.append(i)

abs_min = 10000000

average = float(A_sum / N)

for i in range(len(divisor)):
    abs_temp = abs(divisor[i]-average)
    if abs_temp < abs_min:
        abs_min = abs_temp
        ans = i

print(divisor[ans])

Submission status: Wrong Answer

Solution code:
from sys import stdin

N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
div = []
A_sum = sum(A)
i = 1
while i ** 2 < A_sum:
    if A_sum % i == 0:
        div.append(i)
        div.append(A_sum // i)
    i += 1

div.sort(reverse=True)

for j in div:
    mod = [a % j for a in A]
    mod.sort()
    s = sum(mod)
    print(mod)
    if sum(mod[:-s // j]) <= K:
        print(j)
        break

Submission status: Wrong Answer

Solution code:
import sys
import math
input = sys.stdin.readline

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

S = sum(A)
L = []
for s in range(1, S+1):
    if s > math.sqrt(S) + 1:
        break
    if S % s == 0:
        L.append(S//s)
        L.append(s)
L.sort(reverse = True)

for l in L:
    T = [a%l for a in A]
    T.sort()
    ans = False
    R = []
    r = 0
    for t in T:
        r += t
        R.append(r)
    #print(l, R)
    for i in range(N):
        #print(i, R[-1])
        if R[i] == 0:
            continue
        if R[i] > K:
            break
        if R[N-1] == l*(N-i-1):
            ans = True
            break
        
    if ans:
        print(l)
        break

Submission status: Wrong Answer

Solution code:
import sys
# input = sys.stdin.readline

def main():
  n, k = map(int, input().split())
  alist = list(map(int, input().split()))
  suma = sum(alist)
  i = 1
  yaku = []
  while i*i<=suma:
    if suma % i == 0:
      yaku.append(i)
      if suma//i != i:
        yaku.append(suma//i)
    i += 1

  for d in sorted(yaku, key=lambda x: -x):
    rem = [a%d for a in alist]
    rem = list(sorted(rem))
    sumr = sum(rem)
    kc = 0
    for _r in rem:
      kc += _r
      sumr -= d-_r
      if max(kc, sumr) < k:
        print(d)
        sys.exit(0)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import math
n, k = map(int,input().split())
a = list(map(int, input().split()))

asum = sum(a)
gcdmax = int(math.sqrt(asum))
li = [i for i in range(2,gcdmax+1)]
for i in range(gcdmax,0,-1):
    if asum%i==0:
        li.append(asum//i)


ans = 1
print(li)

for i in li:
    b = [a[ii] % i for ii in range(n)]
    b.sort()
#     print(i,b)
    l = 0
    r = 0
    x = 0
    y = n-1
    while x<=y:
        if r>=l:
            l += b[x]
            x += 1
        else:
            r += i - b[y]
            y -= 1
#         print(l,r)
    if max(l,r) <= k and (l-r)%i==0 :
        ans = i

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math

def get_divisor(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

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

    aSum = sum(A)
    divs = get_divisor(aSum)

    for d in divs:
        r = [a % d for a in A]
        r.sort()
        sumR = sum(r)
        if sumR/2 > K:
            continue

        tmpSum = 0
        for _r in r:
            tmpSum += _r
            op = max(tmpSum, sumR-tmpSum)
            if op <= K:
                print(d)
                sys.exit()

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()

s = sum(A)
i = 1
q1 = []
q2 = []
while i * i <= s :
    if s % i == 0 :
        q1.append(i)
        if i * i != s :
            q2.append(s//i)
    i += 1
prime = q2 + q1[::-1]

def solve() :
    for p in prime :
        m = [a%p for a in A]
        m.sort()
        
        dpl = [0] * N
        dpr = [0] * N
        
        dpl[N-1] = p - m[N-1]
        dpr[0] = m[0]
        for i in range(N-2, -1, -1) :
            dpl[i] = dpl[i+1] + p - m[i]
        for i in range(1, N) :
            dpr[i] = dpr[i-1] + m[i]
        
        for i in range(1, N) :
            if dpl[i] == dpr[i-1] and dpl[i] <= K :
                return p
            
print(solve())

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from copy import deepcopy as dc
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
def divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)
  divisors.sort()
  return divisors
div = divisors(sum(A))
def check(g):
  Atemp = dc(A)
  for i in range(N):
    Atemp[i] %= g
  for i in range(N + 1):
    if max(sum(Atemp[: i]), len(Atemp[i: ]) * g - sum(Atemp[i: ])) <= K:
      return True
  return False

res = 1
for d in div:
  if check(d) == True:
    res = d
print(res)

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
  
from itertools import accumulate

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

sumA = sum(A)
divs = make_divisors(sumA)[::-1]
# 何回操作しても総和が変わらないので，すべての要素を割り切る正の整数は，総和の約数
# よってこれだけ試す

for d in divs:
  B = [a%d for a in A]
  B.sort()
  Bcumsum = list(accumulate(B))
  nBcumsum = list(accumulate([b-d for b in B][::-1]))[::-1]
  for i in range(len(B)-1):
    if Bcumsum[i]==-nBcumsum[i+1]:
      if Bcumsum[i]<=K:
        print(d)
        exit()

Submission status: Wrong Answer

Solution code:
n, K = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = sum(a)
f = []
for i in range(b, 0, -1):
    if b % i == 0:
        f.append(i)

for fi in f:
    a_dif = []
    for i in range(n):
        if a[i] % fi > 0:
            a_dif.append(a[i] % fi)
    if len(a_dif) == 0:
        print(fi)
        break
    a_dif.sort()
    a_dif_rev = [fi-i for i in a_dif]
    former = 0
    latter = sum(a_dif_rev)
    for i in range(n):
        former += a_dif[i]
        latter -= a_dif_rev[i]
        if former == latter:
            cnt = former
            break
    if cnt < K:
        print(fi)
        break

Submission status: Wrong Answer

Solution code:
def calc(N, K, A):
    x = []
    sumA = sum(A)
    for i in range(1, int(sumA ** 0.5) + 1):
        if (sumA % i == 0):
            x += [i]
            if (i != sumA // i):
                x += [sumA // i]
    x.sort()
    x.reverse()
    for y in x:
        cost = []
        pos = []
        neg = []
        for i in range(N):
            a = A[i]
            a_pos = a - (a // y) * y
            a_neg = (a // y + 1) * y - a
            cost += [abs(a_pos - a_neg)]
            pos += [a_pos]
            neg += [a_neg]
        m = 0
        lp = 0
        ln = 0
        ic = 0
        while (True):
            ic += 1
            max_cost = max(cost)
            if (max_cost == -1):
                return y
            i = cost.index(max_cost)
            cost[i] = -1
            if (ic == N):
                if (ln == pos[i]):
                    lp += pos[i]
                elif (lp == neg[i]):
                    ln += neg[i]
            elif (pos[i] < neg[i]):
                lp += pos[i]
            else:
                ln += neg[i]
            if (lp >= ln):
                m += ln
                lp -= ln
                ln = 0
            else:
                m += lp
                ln -= lp
                lp = 0
            if (max(m, lp, ln) > K):
                break
    return 1


(N, K) = tuple([int(s) for s in input().split(' ')])
A = [int(s) for s in input().split(' ')]
print(calc(N, K, A))

Submission status: Wrong Answer

Solution code:
import math
N, K = [int(x) for x in input().split()]
As = [int(x) for x in input().split()]
S = sum(As)
Ds = []
for i in range(1, 1+int(math.sqrt(S))):
  if S % i == 0:
    Ds.append(i)
    Ds.append(S//i)
Ds = sorted(set(Ds))

for d in Ds[::-1]:
#  print(d)
  rs = {}  # Max 500 elements
  for a in As:
    rs[a % d] = rs.get(a % d, 0) + 1
#  print(rs)
  sorted_keys = sorted(rs.keys())
  total = 0
  for i in sorted_keys:
    total += (i-d) * rs[i]
#  print(total)
  num = 0
  for i in sorted_keys:
    total += d * rs[i]
    if total < 0:
      continue
#    print (total, i)
    if total:
      neg = total // (2 * i)
    else:
      neg = 0
    pos = rs[i] - neg
#    print(neg, pos)
    num += neg * (d - i) + pos * i
    break
#  print(num)
  for j in sorted_keys:
    if j < i:
      num += rs[j] * j
    elif j > i:
      num += rs[j] * (d - j)
#    print(num)
  if num <= 2*K:
    print(d)
    exit()
print(1)
exit()
    
  
# 1 2 3 4/-3 -2 -1

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True

def main():
    from math import sqrt, ceil
    N,K = LMIIS()
    A = LMIIS()
    suma = sum(A)
    dL = [0] * N
    dU = [0] * N
    ds = []
    for x in range(N,max(ceil(sqrt(suma)), N)+1):
        
        if suma % x != 0:
            continue

        d = suma // x 
        ds.append(x)
        for i in range(N):
            dL[i] = A[i] % d
        dL.sort()
        for i in range(N):
            dU[i] = d - dL[i]

        c = 0
        l = 0
        r = N-1
        while l < r:
            #print(l,r)
            if dL[l] == dU[r]:
                c += dL[l]
                if c > K:
                    break
                l += 1
                r -= 1
                if l >= N or r < 0:
                    break
            elif dL[l] < dU[r]:
                c += dL[l]
                if c > K:
                    break
                dU[r] -= dL[l]
                l += 1
                if l >= N:
                    break
            else:
                c += dU[r]
                if c > K:
                    break
                dL[l] -= dU[r]
                r -= 1
                if r < 0:
                    break
            
            
        if l >= r:
            print(d)
            return
    print(ds)
    for d in ds[::-1]:
        for i in range(N):
            dL[i] = A[i] % d
        dL.sort()
        for i in range(N):
            dU[i] = d - dL[i]

        c = 0
        l = 0
        r = N-1
        while l < r:
            #print(l,r)
            if dL[l] == dU[r]:
                c += dL[l]
                if c > K:
                    break
                l += 1
                r -= 1
                if l >= N or r < 0:
                    break
            elif dL[l] < dU[r]:
                c += dL[l]
                if c > K:
                    break
                dU[r] -= dL[l]
                l += 1
                if l >= N:
                    break
            else:
                c += dU[r]
                if c > K:
                    break
                dL[l] -= dU[r]
                r -= 1
                if r < 0:
                    break
            
            
        if l >= r:
            print(d)
            return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys, re
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
import bisect

def input(): return sys.stdin.readline().strip()
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, K = MAP()
A = LIST()

def make_divisors(n):
   divisors = []
   for i in range(1, int(n**0.5)+1):
       if n % i == 0:
           divisors.append(i)
           if i != n // i:
               divisors.append(n//i)
   divisors.sort(reverse=True)
   return divisors

for i in make_divisors(sum(A)):
	# print(i)
	r = sorted([x%i for x in A if x%i != 0])
	# print(r)
	if r == []:
		print(i)
		break
	acc = list(accumulate(r))
	for j in range(len(r)-1):  # しきり
		down = acc[j]
		up = i*(len(r)-j-1)-(acc[-1]-acc[j])
		print(down, up)
		if abs(up-down)%i != 0:
			continue
		else:
			if max(up, down) <= K:
				print(i)
				sys.exit(0)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=[int(i) for i in input().split()]

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

s=sum(A)

D=make_divisors(s*(k//s))
D.append(40)
D.sort()
D.reverse()
#print(D)

for m in D:
    now=k
    P=[i%m for i in A]
    P.sort()
    for i in range(n):
        now-=P[i]
        if now<=0:
            now+=P[i]
            ck=i
            break
    else:
        print(m)
        break
    NP=[m-i for i in P]
    now=k
    for i in range(ck,n):
        now-=NP[i]
        if now<0:
            break
    else:
        print(m)
        break

Submission status: Wrong Answer

Solution code:
import sys
import math
input = sys.stdin.readline

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

S = sum(A)
L = []
for s in range(1, S+1):
    if s > math.sqrt(S) + 1:
        break
    if S % s == 0:
        L.append(S//s)
        L.append(s)
L.sort(reverse = True)

for l in L:
    T = [a%l for a in A]
    T.sort()
    ans = False
    R = []
    r = 0
    for t in T:
        r += t
        R.append(r)
    #print(l, R)
    for i in range(N):
        #print(i, R[i])
        if R[i] == 0:
            continue
        if R[i]-R[N-1] == 0:
            ans = True
            break
        if R[i] > K:
            break
    if ans:
        print(l)
        break

Submission status: Wrong Answer

Solution code:
import sys, re
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
import bisect

def input(): return sys.stdin.readline().strip()
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, K = MAP()
A = LIST()

def make_divisors(n):
   divisors = []
   for i in range(1, int(n**0.5)+1):
       if n % i == 0:
           divisors.append(i)
           if i != n // i:
               divisors.append(n//i)
   divisors.sort(reverse=True)
   return divisors

for i in make_divisors(sum(A)):
	# print(i)
	r = sorted([x%i for x in A if x%i != 0])
	# print(r)
	acc = list(accumulate(r))
	for j in range(len(r)-1):  # しきり
		down = acc[j]
		up = i*(len(r)-j-1)-(acc[-1]-acc[j])
		if abs(up-down)%i != 0:
			continue
		else:
			if max(up, down) < K:
				print(i)
				sys.exit(0)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
As = list(map(int, input().split()))
As.sort()
S = sum(As)
#print(S)
if As[N-1]+K >= S:
  print(S)
  exit()
def findd(n):
  for i in range(2, 30000):
    if n%i == 0:
      return i
  return n
M = S
while True:
  P = findd(M)
  M = M//P
  if M == 1:
    print(1)
    break
  Rs = [a%M for a in As]
  Rs.sort()
  s = sum(Rs)
  count = s//M
  r = 0
  for i in range(N-count):
    r += Rs[i]
  if r <= K:
    print(M)
    exit()

Submission status: Wrong Answer

Solution code:
import sys, re
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
import bisect

def input(): return sys.stdin.readline().strip()
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, K = MAP()
A = LIST()

def make_divisors(n):
   divisors = []
   for i in range(1, int(n**0.5)+1):
       if n % i == 0:
           divisors.append(i)
           if i != n // i:
               divisors.append(n//i)
   divisors.sort(reverse=True)
   return divisors

def near(n, x):  # n と最も近い x の倍数は？
	if n-(n//x)*x < (n//x+1)*x-n:
		return (n//x)*x
	else:
		return (n//x+1)*x

for i in make_divisors(sum(A)):
	# print(i)
	r = sorted([x%i for x in A if x%i != 0])
	# print(r)
	if r == []:
		print(i)
		break
	acc = list(accumulate(r))
	for j in range(len(r)-1):  # しきり
		down = acc[j]
		up = i*(len(r)-j-1)-(acc[-1]-acc[j])
		if abs(up-down)%i != 0:
			continue
		else:
			if max(up, down) < K:
				print(i)
				sys.exit(0)

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

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

#print(make_divisors(sum(A)))
for d in make_divisors(sum(A)):
  if d==1:
    print(d)
    exit()
  if (max(A)%d)+K < d:
    continue
  A_ = [a%d for a in A if a%d]
  A_.sort()
  left, right = 0, len(A_)-1
  for k in range(K):
#    print(d, A_)
    if sum([a%d for a in A_]) == 0:
      print(d)
      exit()
    
    A_[left] -= 1
    if A_[left]==0:
      left += 1
    A_[right]+= 1
    if A_[right]==d:
      right-= 1

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-


def get_fact(N):
  ret = set([N])
  for i in range(2,int(N**0.5)+2):
    if N%i == 0:
      ret.add(i)
      ret.add(N//i)
  return ret


def main():
  ## input
  N,K = map(int, input().split())
  An = list(map(int, input().split()))

  ## Solve
  fset = get_fact(sum(An))
  ans = 1
  for f in sorted(fset):
    Amod = []
    for a in An:
      if a%f > 0:
        Amod.append(a%f)
    if len(Amod)==0:
      ans = f
    else:
      Amod = sorted(Amod)
      for i in range(1,len(Amod)):
        Amod[i] += Amod[i-1]
      for i in range(len(Amod)):
        if max(Amod[i],abs(f*(N-i-1)-Amod[-1]-Amod[i])) <= K:
          ans = f
  return ans


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