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:
# https://atcoder.jp/contests/abc136/submissions/6708242

def solve():
    n, k = map(int, input().split())
    a = tuple(sorted(map(int, input().split()), reverse=True))

    sum_a = sum(a)
    e = set()
    divisor = 1
    while divisor * divisor <= sum_a:
        if sum_a % divisor == 0:
            e.add(divisor)
            e.add(sum_a // divisor)
        divisor += 1

    e = sorted(e, reverse=True)
    # 約数降順

    for cand in e:
        r = tuple(sorted(x % cand for x in a if x % cand != 0))

        accm = [0]
        t = 0
        for x in r:
            t += x
            accm.append(t)

        accp = [0]
        t = 0
        for x in r:
            t += cand - x
            accp.append(t)

        m = len(r)
        for i in range(m):
            if (accm[i] == (accp[m] - accp[i])) and (accm[i] <= k):
                return cand
    return -1


print(solve())

# 操作で総和は不変

Submission status: Wrong Answer

Solution code:
n,l=map(int,input().split())
A=list(map(int,input().split()))
S=sum(A)
def div(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 range(len(div(S))):
  b=[]
  c=[]
  for j in range(n):
    b.append(A[j]%(div(S)[i]))
    c.append(div(S)[i]-A[j]%(div(S)[i]))
  b=sorted(b)
  c=sorted(c)
  B=[0]
  C=[0]
  for j in range(n):
    B.append(B[-1]+b[j])
    C.append(C[-1]+c[j])
  B.pop(0)
  C.pop(0)
  j=0
  k=0
  for j in range(n):
    if B[j]==C[n-j-2]:
      d=B[j]
      if d<=l:
        print(div(S)[i])
        exit()

Submission status: Wrong Answer

Solution code:
n,l=map(int,input().split())
A=list(map(int,input().split()))
S=sum(A)
def div(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 range(len(div(S))):
  b=[]
  c=[]
  for j in range(n):
    b.append(A[j]%(div(S)[i]))
    c.append(div(S)[i]-A[j]%(div(S)[i]))
  b=sorted(b)
  c=sorted(c)
  B=[0]
  C=[0]
  for j in range(n):
    B.append(B[-1]+b[j])
    C.append(C[-1]+c[j])
  B.pop(0)
  C.pop(0)
  j=0
  k=0
  while j<n:
    while k<n:
      
      if B[j]<C[k]:
        j=j+1
        if k!=0:
          k=k-1
        continue
      elif B[j]>C[k]:
        k=k+1
      if B[j]==C[k]:
        d=B[j]
        if d<=l:
          print(div(S)[i])
          exit()
        break
    else:
      continue
    break

Submission status: Wrong Answer

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

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

d=make_divisors(s)
d.reverse()
for y in d:
    r=[]
    for x in a:
        if x%y==0:
            continue
        r.append(x%y)
    r.sort()
    print(y)
    wa=[0]
    for x in r:
        wa.append((wa[-1]+x)%y)
    print(r)
    print(wa)

Submission status: Wrong Answer

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

def searchPrimeNum(N):
    max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

plis = searchPrimeNum(40000)

lis = []
for p in plis:
    if S%p == 0:
        lis.append([p,1])
        S = S//p
        while S%p == 0:
            lis[-1][1] += 1
            S = S//p
    if S == 1:
        break
if S != 1:
    lis =[[S,1]]

yakulis =[1]
for l in lis:
    for j in range(len(yakulis)):
        for k in range(l[1]):
            n = yakulis[j]
            yakulis.append(l[0]**(k+1)*n)

yakulis.sort(reverse=True)

s = True
for r in yakulis:
    B = [i%r for i in A]
    B.sort()
    le = -1
    ri = N
    while ri-le > 1:
        mid = (le+ri)//2
        pl = sum(B[:mid+1])
        mi = r*(N-1-mid) - sum(B[mid+1:])
        if pl > mi:
            ri = mid
        else:
            le = mid
    k = sum(B[:le+1])
    if k <= K:
        s = False
        print(r)
        break
if s:
    print(1)

Submission status: Wrong Answer

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

def searchPrimeNum(N):
    max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

plis = searchPrimeNum(30000)

lis = []
for p in plis:
    if S%p == 0:
        lis.append([p,1])
        S = S//p
        while S%p == 0:
            lis[-1][1] += 1
            S = S//p
    if S == 1:
        break

yakulis =[1]
for l in lis:
    for j in range(len(yakulis)):
        for k in range(l[1]):
            n = yakulis[j]
            yakulis.append(l[0]**(k+1)*n)

yakulis.sort(reverse=True)

s = True
for r in yakulis:
    B = [i%r for i in A]
    B.sort()
    le = -1
    ri = N
    while ri-le > 1:
        mid = (le+ri)//2
        pl = sum(B[:mid+1])
        mi = r*(N-1-mid) - sum(B[mid+1:])
        if pl > mi:
            ri = mid
        else:
            le = mid
    while sum(B[:le+1]) != r*(N-1-le) - sum(B[le+1:]):
        None
    k = sum(B[:le+1])
    if k <= K:
        s = False
        print(r)
        break
if s:
    print(1)

Submission status: Wrong Answer

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

def searchPrimeNum(N):
    max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

plis = searchPrimeNum(30000)

lis = []
for p in plis:
    if S%p == 0:
        lis.append([p,1])
        S = S//p
        while S%p == 0:
            lis[-1][1] += 1
            S = S//p
    if S == 1:
        break

yakulis =[1]
for l in lis:
    for j in range(len(yakulis)):
        for k in range(l[1]):
            n = yakulis[j]
            yakulis.append(l[0]**(k+1)*n)

yakulis.sort(reverse=True)

s = True
for r in yakulis:
    B = [i%r for i in A]
    B.sort()
    le = -1
    ri = N
    while ri-le > 1:
        mid = (le+ri)//2
        pl = sum(B[:mid+1])
        mi = r*(N-1-mid) - sum(B[mid+1:])
        if pl > mi:
            ri = mid
        else:
            le = mid
    k = sum(B[:le+1])
    if k <= K:
        s = False
        print(r)
        break
if s:
    print(1)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    sum_A=sum(A)
    divisor_A=[]
    i=1
    while i**2 <= sum_A:
        if sum_A%i == 0:
            divisor_A.append(i)
            if i**2 != sum_A:
                divisor_A.append(sum_A//i)
        i+=1
    ans=0
    for x in divisor_A:
        sumabsdif=0
        sumdif=0
        h=[]
        for a in A:
            p=a%x
            if p==min(p,-(p-x)):
                sumabsdif+=p
                sumdif+=p
                heappush(h,-p)
            else:
                sumabsdif+=-(p-x)
                sumdif+=p-x
                heappush(h,p-x)
        for _ in range(abs(sumdif)//x):
            sumabsdif+=x+heappop(h)*2
        if sumabsdif//2 <= K:
            ans=max(ans,x)
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    sum_A=sum(A)
    divisor_A=[]
    i=1
    while i**2 <= sum_A:
        if sum_A%i == 0:
            divisor_A.append(i)
        i+=1
    ans=0
    for x in divisor_A:
        y=sum_A//x
        sumabsdif=0
        sumdif=0
        h=[]
        for a in A:
            p=a%x
            if p==min(p,abs(p-x)):
                sumabsdif+=p
                sumdif+=p
                heappush(h,-p)
            else:
                sumabsdif+=abs(p-x)
                sumdif-=abs(p-x)
                heappush(h,-abs(p-x))
        q=0
        for _ in range(abs(sumdif)//x):
            q+=x+heappop(h)*2
        if (q+sumabsdif)//2 <= K:
            ans=max(ans,x)
        sumabsdif=0
        sumdif=0
        h=[]
        for a in A:
            p=a%y
            if p==min(p,abs(p-y)):
                sumabsdif+=p
                sumdif+=p
                heappush(h,-p)
            else:
                sumabsdif+=abs(p-y)
                sumdif-=abs(p-y)
                heappush(h,-abs(p-y))
        q=0
        for _ in range(abs(sumdif)//y):
            q+=y+heappop(h)*2
        if (q+sumabsdif)//2 <= K:
            ans=max(ans,y)
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    sum_A=sum(A)
    divisor_A=[]
    i=1
    while i**2 < sum_A:
        if sum_A%i == 0:
            divisor_A.append(i)
        i+=1
    ans=0
    for x in divisor_A:
        y=sum_A//x
        sumabsdif=0
        sumdif=0
        h=[]
        for a in A:
            p=a%x
            if p==min(p,abs(p-x)):
                sumabsdif+=p
                sumdif+=p
                heappush(h,-p)
            else:
                sumabsdif+=abs(p-x)
                sumdif-=abs(p-x)
                heappush(h,-abs(p-x))
        q=0
        for _ in range(abs(sumdif)//x):
            q+=x+heappop(h)*2
        if (q*2+sumabsdif)//2 <= K:
            ans=max(ans,x)
        sumabsdif=0
        sumdif=0
        h=[]
        for a in A:
            p=a%y
            if p==min(p,abs(p-y)):
                sumabsdif+=p
                sumdif+=p
                heappush(h,-p)
            else:
                sumabsdif+=abs(p-y)
                sumdif-=abs(p-y)
                heappush(h,-abs(p-y))
        q=0
        for _ in range(abs(sumdif)//y):
            q+=y+heappop(h)*2
        if (q*2+sumabsdif)//2 <= K:
            ans=max(ans,y)
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    sum_A=sum(A)
    divisor_A=[]
    i=1
    while i**2 < sum_A:
        if sum_A%i == 0:
            divisor_A.append(i)
        i+=1
    ans=0
    for x in divisor_A:
        y=sum_A//x
        sumabsdif=0
        sumdif=0
        h=[]
        for a in A:
            p=a%x
            if p==min(p,abs(p-x)):
                sumabsdif+=p
                sumdif+=p
                heappush(h,-p)
            else:
                sumabsdif+=abs(p-x)
                sumdif-=abs(p-x)
                heappush(h,-abs(p-x))
        q=0
        for _ in range(abs(sumdif)//x):
            q+=x+heappop(h)*2
        if (q+sumabsdif)//2 <= K:
            ans=max(ans,x)
        sumabsdif=0
        sumdif=0
        h=[]
        for a in A:
            p=a%y
            if p==min(p,abs(p-y)):
                sumabsdif+=p
                sumdif+=p
                heappush(h,-p)
            else:
                sumabsdif+=abs(p-y)
                sumdif-=abs(p-y)
                heappush(h,-abs(p-y))
        q=0
        for _ in range(abs(sumdif)//y):
            q+=y+heappop(h)*2
        if (q*2+sumabsdif)//2 <= K:
            ans=max(ans,y)
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    sum_A=sum(A)
    divisor_A=[]
    i=1
    while i**2 < sum_A:
        if sum_A%i == 0:
            divisor_A.append(i)
        i+=1
    ans=0
    for x in divisor_A:
        y=sum_A//x
        sumabsdif=0
        sumdif=0
        h=[]
        for a in A:
            p=a%x
            if p==min(p,abs(p-x)):
                sumabsdif+=p
                sumdif+=p
                heappush(h,-p)
            else:
                sumabsdif+=abs(p-x)
                sumdif-=abs(p-x)
                heappush(h,-abs(p-x))
        q=0
        for _ in range(abs(sumdif)//x):
            q+=x+heappop(h)*2
        if (q+sumabsdif)//2 <= K:
            ans=max(ans,x)
        sumabsdif=0
        sumdif=0
        h=[]
        for a in A:
            p=a%y
            if p==min(p,abs(p-y)):
                sumabsdif+=p
                sumdif+=p
                heappush(h,-p)
            else:
                sumabsdif+=abs(p-y)
                sumdif-=abs(p-y)
                heappush(h,-abs(p-y))
        q=0
        for _ in range(abs(sumdif)//y):
            q+=y+heappop(h)*2
        if (q+sumabsdif)//2 <= K:
            ans=max(ans,y)
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    sum_A=sum(A)
    divisor_A=[]
    i=1
    while i**2 < sum_A:
        if sum_A%i == 0:
            divisor_A.append(i)
        i+=1
    ans=0
    for x in divisor_A:
        y=sum_A//x
        sumabsdif=0
        sumdif=0
        h=[]
        for a in A:
            p=a%x
            if p==min(p,abs(p-x)):
                sumabsdif+=p
                sumdif+=p
                heappush(h,-p)
            else:
                sumabsdif+=abs(p-x)
                sumdif-=abs(p-x)
                heappush(h,-abs(p-x))
        q=0
        for _ in range(abs(sumdif)//x):
            q+=x+heappop(h)
        if (q+sumabsdif)//2 <= K:
            ans=max(ans,x)
        sumabsdif=0
        sumdif=0
        h=[]
        for a in A:
            p=a%y
            if p==min(p,abs(p-y)):
                sumabsdif+=p
                sumdif+=p
                heappush(h,-p)
            else:
                sumabsdif+=abs(p-y)
                sumdif-=abs(p-y)
                heappush(h,-abs(p-y))
        q=0
        for _ in range(abs(sumdif)//y):
            q+=y+heappop(h)
        if (q+sumabsdif)//2 <= K:
            ans=max(ans,y)
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    sum_A=sum(A)
    divisor_A=[]
    i=1
    while i**2 < sum_A:
        if sum_A%i == 0:
            divisor_A.append(i)
        i+=1
    ans=0
    for x in divisor_A:
        y=sum_A//x
        sumabsdif=0
        sumdif=0
        h=[]
        for a in A:
            p=a%x
            if p==min(p,abs(p-x)):
                sumabsdif+=p
                sumdif+=p
                heappush(h,-p)
            else:
                sumabsdif+=abs(p-x)
                sumdif-=abs(p-x)
                heappush(h,-abs(p-x))
        q=0
        for _ in range(sumabsdif//x):
            q+=x+heappop(h)
        if (q+abs(sumdif))//2 <= K:
            ans=max(ans,x)
        sumabsdif=0
        sumdif=0
        h=[]
        for a in A:
            p=a%y
            if p==min(p,abs(p-y)):
                sumabsdif+=p
                sumdif+=p
                heappush(h,-p)
            else:
                sumabsdif+=abs(p-y)
                sumdif-=abs(p-y)
                heappush(h,-abs(p-y))
        q=0
        for _ in range(-(-sumabsdif//y)):
            q+=y+heappop(h)
        if (q+abs(sumdif))//2 <= K:
            ans=max(ans,y)
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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


def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    divisors = sorted(divisors)
    return divisors

n, k = LI()
A = LI()
for gcd in make_divisors(sum(A)):
    d_remainder = sorted([a % gcd for a in A if a % gcd])
    u_remainder = list(accumulate([gcd - i for i in d_remainder][::-1]))[::-1]
    d_remainder = list(accumulate(d_remainder))
    if not d_remainder:
        ans = gcd
    else:
        for i in range(len(u_remainder)):
            if d_remainder[i] == u_remainder[i + 1]:
                if d_remainder[i] <= k:
                    ans = gcd
                    break
                else:
                    print(ans)
                    exit()

print(ans)

Submission status: Wrong Answer

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

sm = sum(A)

divs = []

for i in range(1, sm):
    if sm % i == 0:
        divs.append(i)
        divs.append(sm // i)
    if i * i > sm:
        break

divs.sort()

result = 1

for d in divs[::-1]:
    ts1 = []
    ts2 = []
    for n in A:
        x = n % d
        if x < d - x:
            ts1.append(x)
        else:
            ts2.append(x - d)
    if sum(ts1) == -sum(ts2):
        ts = sum(ts1)
    else:
        ts = max(sum(sorted(ts1)[:-1]), -sum(sorted(ts2)[1:]))
    #print(d, ts1, ts2, ts)
    if ts <= K:
        result = d
        break

print(result)

Submission status: Wrong Answer

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

sm = sum(A)

divs = []

for i in range(1, sm):
    if sm % i == 0:
        divs.append(i)
        divs.append(sm // i)
    if i * i > sm:
        break

divs.sort()

result = 1

for d in divs[::-1]:
    ts = []
    for n in A:
        x = n % d
        ts.append(min(x, d - x))
    ts.sort()
    if sum(ts[:-1]) <= K:
        result = d
        break

print(result)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys

n,k = map(int,input().split())
al = list(map(int,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)
    return divisors

divisors = sorted(make_divisors(sum(al)), reverse=True)

for i in divisors:
    point = 0
    div_l = sorted([a%i for a in al])
    while div_l:
        if div_l[0] < i - div_l[-1]:
            div_l[-1] += div_l[0]
            point += div_l[0]
            div_l.pop(0)
        else:
            div_l[0] -= (i - div_l[-1])
            point += i - div_l[-1]
            div_l.pop(-1)
            
    
    if point <= 2*k:
        print(i)
        sys.exit()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys

n,k = map(int,input().split())
al = list(map(int,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)
    return divisors

divisors = sorted(make_divisors(sum(al)), reverse=True)

for i in divisors:
    point = 0
    div_l = [a%i for a in al]
    while div_l:
        if div_l[0] < i - div_l[-1]:
            div_l[-1] += div_l[0]
            point += div_l[0]
            div_l.pop(0)
        else:
            div_l[0] -= (i - div_l[-1])
            point += i - div_l[-1]
            div_l.pop(-1)
            
    
    if point <= 2*k:
        print(i)
        sys.exit()

Submission status: Wrong Answer

Solution code:
import sys
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)
l = []

def check(b) :
    r1 = [x % b for x in a]
    r1.sort()
    s1 = sum(r1)
    
    mn = 1e9
    s2 = 0
    for i in range(n):
        s2 += r1[i]
        mn = min(max(s2, (n-1-i)*b - (s1-s2)), mn)
        
    if mn <= k :
        print(int(b))
        sys.exit(0)
        

for p in range(1,int((s+1)**0.5+1)) :
    if s % p != 0:
        continue
    b = s // p
    l.append(p)
    l.append(b)
l.reverse()

for b in l:
    check(b)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
s=sum(l)
yaku=[]
for i in range(1,round(s**0.5)+1):
    if s%i==0:
        yaku.append(i)
        yaku.append(s//i)
yaku.sort(reverse=True)
for i in yaku:
    p=0
    l=sorted(l,key=lambda x: min(x%i,i-x%i))
    for j in range(len(l)-1):
        p+=min(j%i,i-j%i)
    if 2*p<=k:
        print(i)
        exit()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
s=sum(l)
yaku=[]
for i in range(1,round(s**0.5)+1):
    if s%i==0:
        yaku.append(i)
        yaku.append(s//i)
yaku.sort(reverse=True)
for i in yaku:
    p=0
    for j in l:
        p+=min(j%i,i-j%i)
    if p<=k:
        print(i)
        exit()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def divisors(n):
    S,T=[],[]
    for i in range(1,int(n**.5)+1):
        if n%i==0:
            S.append(i)
            T.append(n//i)
    T.reverse()
    return S+T if S[-1]!=T[0] else S+T[1:]

def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    D=divisors(sum(A))
    def check(d):
        plus=0
        minus=0
        cost=0
        for i in range(n-1):
            q=A[i]//d
            p=abs(q*(d+1)-A[i])
            m=abs(A[i]-q*d)
            if(p<m): plus+=p
            else: minus+=m
        cost=min(plus,minus)
        plus-=cost; minus-=cost
        cost+=max(plus,minus)
        return cost<=k
    ans=1
    for d in D:
        if(check(d)): ans=d
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def divisors(n):
    S,T=[],[]
    for i in range(1,int(n**.5)+1):
        if n%i==0:
            S.append(i)
            T.append(n//i)
    T.reverse()
    return S+T if S[-1]!=T[0] else S+T[1:]

def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    D=divisors(sum(A))
    def check(d):
        cost=0
        for i in range(n-1):
            q=A[i]//d
            cost+=min(abs(A[i]-q*d),abs(A[i]-q*(d+1)))
        return cost<=k
    ans=1
    for d in D:
        if(check(d)): ans=d
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def divisors(n):
    S,T=[],[]
    for i in range(1,int(n**.5)+1):
        if n%i==0:
            S.append(i)
            T.append(n//i)
    T.reverse()
    return S+T if S[-1]!=T[0] else S+T[1:]

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if discrete else 10**-12
    if((not left)^f(r)): return r if left else r+1
    elif(left^f(l)): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if not discrete else l if left else r

def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    D=divisors(sum(A))
    def check(ind):
        d=D[ind]
        cost=0
        for i in range(n-1):
            q=A[i]//d
            cost+=min(abs(A[i]-q*d),abs(A[i]-q*(d+1)))
        return cost<=k

    i=bisection(0,len(D)-1,check)
    print(D[i])
resolve()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

s=sum(A)
n=int(s**0.5)

#約数のリスト
cd=[]

for i in range(1,n+2):
	if s%i==0:
		cd.append(i)
		cd.append(s/i)

cd.sort(reverse=True)

def check(t):
	A_temp=[]
	for x in A:
		A_temp.append(x%t)

	A_temp.sort()

	#Aの配列をmod tした配列A_tempの累積和
	A_temp_sum=[]

	for i,x in enumerate(A_temp):
		if i==0: A_temp_sum.append(x)
		else: A_temp_sum.append(A_temp_sum[-1]+x)

	#配列の前半は、数字をマイナスしていく
	p1=min(bisect_left(A_temp_sum,K),N-2)
	if A_temp_sum[p1]<=K:
		k1=A_temp_sum[p1]
	else:
		p1-=1
		k1=A_temp_sum[p1]

	#配列の後半で、数字をどれだけプラスする必要があるか
	k2=t*(N-p1-1)-(A_temp_sum[-1]-A_temp_sum[p1])

	#プラスする量が、マイナスする量より少なければ成立
	if k2<=k1:
		return True
	else:
		return False

for x in cd:
	if check(x):
		print x
		quit()

Submission status: Wrong Answer

Solution code:
import sys,os,math
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import Queue



# n, k = map(int, raw_input().split())
# da = map(int, raw_input().split())
# db = map(int, raw_input().split())


def main():
    n, k = map(int, raw_input().split())
    da = map(int, raw_input().split())
    sm = sum(da)
    mx = max(da)
    ans = -1
    for i in range(1, int(math.sqrt(sm))+1):
        # print i
        if sm%i==0:
            def check(p):
                if p >= mx:
                    return False
                sk = 0
                for num in da:
                    l, r = (num/p)*p, (num/p+1)*p
                    sk += min(num-l, r-num)
                return sk<=k*2
            # print check(7), 7777777
            if check(i):
                ans = max(ans, i)
            if check(sm/i):
                ans = max(ans, sm/i)

    print ans






main()

Submission status: Wrong Answer

Solution code:
import sys,os,math
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import Queue



# n, k = map(int, raw_input().split())
# da = map(int, raw_input().split())
# db = map(int, raw_input().split())


def main():
    n, k = map(int, raw_input().split())
    da = map(int, raw_input().split())
    sm = sum(da)
    ans = -1
    fac = set()
    for i in range(1, int(math.sqrt(sm))+1):
        # print i
        if sm%i==0:
            def check(p):
                sk = 0
                for num in da:
                    l, r = (num/p)*p, (num/p+1)*p
                    sk += min(num-l, r-num)
                sk/=2
                return sk<=k
            # print check(7), 7777777
            if check(i):
                ans = max(ans, i)
            if check(sm/i):
                ans = max(ans, sm/i)

    print ans






main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,K = map(int,readline().split())
A = np.array(read().split(),np.int64)

S = A.sum()

def test(d):
    # 全部をdの倍数に作り替えることができる
    B = A%d
    B.sort()
    # 繰り上がるものの個数
    x = B.sum() // d
    cnt = d*x - B[::-1][::x+1].sum()
    return cnt <= K

# S の約数を取得
U = 3*10**4
x = np.arange(1,U)
div = x[S%x==0]
div = np.union1d(div,S//div)

for x in div[::-1]:
    if test(x):
        break

print(x)

Submission status: Wrong Answer

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

S = sum(A)
div = [1]
n = 2
ans = 1
while n <= S:
    if S % n == 0:
        s = 0
        for a in A[:-1]:
            x = a % n
            s += a % n
        if s / 2 <= K:
            ans = n

    n += 1

print(ans)