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: Time Limit Exceeded

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)]
li2 = [asum//i for i in range(gcdmax,0,-1)]
li = li + li2

ans = 1

for i in li:
    b = [a[ii] % i for ii in range(n)]
    b.sort()
    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
    if max(l,r) <= k and (l-r)%i==0 :
        ans = i

print(ans)

Submission status: Time Limit Exceeded

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

asum = sum(a)
gcdmax = int(math.sqrt(asum))


ans = 1
# print(a)

for i in range(2,asum+1):
    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: Time Limit Exceeded

Solution code:
import sys
import math
MAX_INT = int(10e9)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def judge(x):
  l = []
  for i in range(N):
    l.append(a[i]%x)
  l.sort()

  aa = 0
  bb = 0
  for i in l:
    tmp = i
    if aa + tmp > K:
      bb += x-tmp
      if bb > K:
        return False
    else:
      aa += tmp
  else:
    return True

N,K = IL()
a = IL()
num = sum(a)
ans = []

for i in range(num,int(math.sqrt(num)-1),-1):
  if num%i == 0:
    if judge(i):
      print(i)
      exit()
    if judge(num//i):
      ans.append(num//i)

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
MAX_INT = int(10e9)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def judge(x):
  l = []
  for i in range(N):
    l.append(a[i]%x)
  l.sort()

  aa = 0
  bb = 0
  for i in l:
    tmp = i
    if aa + tmp > K:
      bb += x-tmp
      if bb > K:
        return False
    else:
      aa += tmp
  else:
    return True

N,K = IL()
a = IL()
a.sort()
num = sum(a)
ans = []

for i in range(num,int(math.sqrt(num)-1),-1):
  if num%i == 0:
    if judge(i):
      ans.append(i)
    if judge(num//i):
      ans.append(num//i)

ans.sort()
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import math
MAX_INT = int(10e9)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def judge(x,list):
  l = np.array(list) %x
  l.sort()
  aa = 0
  bb = 0
  for i in l:
    tmp = i
    if aa + tmp > K:
      bb += x-tmp
      if bb > K:
        return False
    else:
      aa += tmp
  else:
    return True

N,K = IL()
a = IL()
a.sort()
num = sum(a)
ans = []

for i in range(num,int(math.sqrt(num)-1),-1):
  if num%i == 0:
    if judge(i,a):
      ans.append(i)
    if judge(num//i,a):
      ans.append(num//i)

ans.sort()
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,K = map(int,input().split())
A = list(map(int,input().split()))
S = sum(A)
ans = 1
C = []
for i in range(1,int(S**0.5+1)):
    if S%i == 0:
        C.append(i)
        C.append(S//i)
for c in C:
    B = np.array(A) % c
    B.sort()
    hoge = 0
    for i in range(N):
        hoge += B[i]
        if hoge <= K and hoge == -sum(B[i+1:]-c):
            ans = max(ans,c)
print(ans)

Submission status: Time Limit Exceeded

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(1,ceil(sqrt(suma))+1):
    for x in range(1,suma):
        
        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

    for i  in range(len(ds)-1,-1,-1):
        d = ds[i]
        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: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

    N,K = LMIIS()
    A = LMIIS()
    suma = sum(A)
    dL = [0] * N
    dU = [0] * N
    for x in range(1,suma+1):
        
        if suma % x != 0:
            continue

        d = suma // 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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    N,K = LMIIS()
    A = LMIIS()
    suma = sum(A)
    for x in range(1,suma+1):
        
        if suma % x != 0:
            continue
        d = suma // x
    
        dL = [0] * N
        dU = [0] * N
        for i in range(N):
            dL[i] = A[i] % d
            dU[i] = d - A[i] % d

        dL.sort()
        dU.sort(reverse=True)
        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: Time Limit Exceeded

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()
    cnt = 1
    while len(a_dif) > 0:
        a_dif[0] -= 1
        if a_dif[0] == 0:
            del a_dif[0]
        a_dif[-1] = (a_dif[-1]+1)%fi
        if a_dif[-1] == 0:
            del a_dif[-1]
        cnt += 1
        if cnt > K:
            break
    if len(a_dif) == 0:
        print(fi)
        break

Submission status: Time Limit Exceeded

Solution code:
def get_prime_factorized(N):
    result    = []
    base, exp = 2, 0
    while base ** 2 <= N:
        while N % base == 0:
            N    = N // base
            exp += 1
        if exp > 0:
            result.append([base, exp])
        base, exp = base + 1, 0
    if N > 1:
        result.append([N, 1])
    return result

def re_func_divisior(prime_factorized):
    base, exp = prime_factorized.pop()
    P = re_func_divisior(prime_factorized) if prime_factorized else [[]]
    Q = [[base ** k] for k in range(exp + 1)]
    return [p + q for p in P for q in Q]

def get_list_divisor(N, reverse=True):
    try:
        prime_factorized = get_prime_factorized(N)
        res    = re_func_divisior(prime_factorized)
        result = []
        for k in res:
            for i, x in enumerate(k):
                if i == 0:
                    r = x
                else:
                    r *= x
            result.append(r)
        result = sorted(result, reverse=reverse)
    except:
        result = [N]
    return result


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

X = get_list_divisor(sum(A))

is_break = False

for x in X:
    POS = sorted([a % x for a in A if a % x != 0])
    NEG = [x - pos for pos in POS]
    for sep in range(1, len(POS)):
        sum_POS = sum(POS[:sep])
        if sum_POS == sum(NEG[sep:]) and sum_POS <= K:
            is_break = True
            break
    if is_break:
        break

print(x)

Submission status: Time Limit Exceeded

Solution code:
import math
a,b=map(int,input().split())
c=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)

    #divisors.sort()
    return divisors
d=make_divisors(sum(c))


m=1
for i in d:
  d=[0 for j in range(a)]
  for j in range(a):
    d[j]=c[j]%i
  d.sort()
  for j in range(a):
    k=sum(d[:j]) 
    l=(a-j)*i-sum(d[j:])
    if k==l and k+l<=b*2:
      m=max(i,m)
      break
print(m)

Submission status: Time Limit Exceeded

Solution code:
def get_prime_factorized(N):
    result    = []
    base, exp = 2, 0
    while base ** 2 <= N:
        while N % base == 0:
            N    = N // base
            exp += 1
        if exp > 0:
            result.append([base, exp])
        base, exp = base + 1, 0
    if N > 1:
        result.append([N, 1])
    return result

def re_func_divisior(prime_factorized):
    base, exp = prime_factorized.pop()
    P = re_func_divisior(prime_factorized) if prime_factorized else [[]]
    Q = [[base ** k] for k in range(exp + 1)]
    return [p + q for p in P for q in Q]

def get_list_divisor(N, reverse=True):
    try:
        prime_factorized = get_prime_factorized(N)
        res    = re_func_divisior(prime_factorized)
        result = []
        for k in res:
            for i, x in enumerate(k):
                if i == 0:
                    r = x
                else:
                    r *= x
            result.append(r)
        result = sorted(result, reverse=reverse)
    except:
        result = [N]
    return result


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

X = get_list_divisor(sum(A))

is_break = False

for x in X:
    POS = sorted([a % x for a in A if a % x != 0])
    NEG = [x - pos for pos in POS]
    for sep in range(1, len(POS)):
        if sum(POS[:sep]) == sum(NEG[sep:]) and sum(POS[:sep]) <= K:
            is_break = True
            break
    if is_break:
        break

print(x)

Submission status: Time Limit Exceeded

Solution code:
def get_prime_factorized(N):
    result    = []
    base, exp = 2, 0
    while base ** 2 <= N:
        while N % base == 0:
            N    = N // base
            exp += 1
        if exp > 0:
            result.append([base, exp])
        base, exp = base + 1, 0
    if N > 1:
        result.append([N, 1])
    return result

def re_func_divisior(prime_factorized):
    base, exp = prime_factorized.pop()
    P = re_func_divisior(prime_factorized) if prime_factorized else [[]]
    Q = [[base ** k] for k in range(exp + 1)]
    return [p + q for p in P for q in Q]

def get_list_divisor(N, reverse=True):
    try:
        prime_factorized = get_prime_factorized(N)
        res    = re_func_divisior(prime_factorized)
        result = []
        for k in res:
            for i, x in enumerate(k):
                if i == 0:
                    r = x
                else:
                    r *= x
            result.append(r)
        result = sorted(result, reverse=reverse)
    except:
        result = [N]
    return result


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

X = get_list_divisor(sum(A))

is_break = False

for x in X:
    POS = sorted([a % x for a in A if a % x != 0])
    NEG = [x - pos for pos in POS]
    for sep in range(1, len(POS)):
        if sum(POS[:sep]) == sum(NEG[sep:]) and sum(POS[:sep]) <= K:
            is_break = True
            break
    if is_break:
        break

print(x)

Submission status: Time Limit Exceeded

Solution code:
import math
a,b=map(int,input().split())
c=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)

    divisors.sort()
    return divisors
d=make_divisors(sum(c))


m=1
for i in d:
  d=[0 for i in range(a)]
  for j in range(a):
    d[j]=c[j]%i
  d.sort()
  for j in range(a):
    k=sum(d[:j]) 
    l=(a-j)*i-sum(d[j:])
    if k==l and k+l<=b*2:
      m=i
      break
print(m)

Submission status: Time Limit Exceeded

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

import sys
from math import sqrt
from collections import deque

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 INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,K=MAP()
A=LIST()

sm=sum(A)

def divisor_set(N: int) -> set:
    """ 約数の列挙・個数 """
    # 1とその数はデフォで入れとく
    s = {1, N}
    # 終点はルート切り捨て
    for i in range(2, int(sqrt(N))+1):
        # 割り切れるなら、iとN/iを追加
        if N % i == 0:
            s.add(i)
            s.add(N // i)
    return s

divs=sorted(divisor_set(sm), reverse=True)

for div in divs:
    B=[]
    for i in range(N):
        if A[i]%div!=0:
            B.append(A[i]%div)
    B.sort()
    B=deque(B)
    cnt=0
    while len(B):
        B[0]-=1
        B[-1]+=1
        if B[0]%div==0:
            B.popleft()
        if B[-1]%div==0:
            B.pop()
        cnt+=1
    if cnt<=K:
        print(div)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import math
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def get_divisors(n):
    """
    n の約数をリストで返す
    :param int n:
    :rtype: list of int
    """
    ret = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            ret.append(i)
            if n // i != i:
                ret.append(n // i)
    return ret


def can_make(div):
    mods = []
    for a in A:
        mods.append(a % div)

    mods.sort()
    left = 0
    right = len(mods) - 1
    for k in range(K + 1):
        while left < len(mods) and mods[left] % div == 0:
            left += 1
        while right >= 0 and mods[right] % div == 0:
            right -= 1
        if right < left:
            return True
        mods[left] -= 1
        mods[right] += 1
    return False


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

# 答えは絶対 A の合計の約数になる
divs = get_divisors(sum(A))
for div in sorted(divs, reverse=True):
    if can_make(div):
        print(div)
        exit()
assert False

Submission status: Time Limit Exceeded

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

N, K = [int(item) for item in input().split()]
A = [int(item) for item in input().split()]

for v in range(max(A) + K, 0, -1):
    sum_m = []
    for a in A:
        sum_m.append(a % v)
    if sum(sum_m) % v == 0:
        if sum(sum_m) - max(sum_m) <= K:
            print(v)
            break

Submission status: Time Limit Exceeded

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

N, K = [int(item) for item in input().split()]
A = [int(item) for item in input().split()]

for v in range(sum(A), 0, -1):
    sum_m = []
    for a in A:
        sum_m.append(a % v)
    if sum(sum_m) % v == 0:
        if sum(sum_m) - max(sum_m) <= K:
            print(v)
            break

Submission status: Time Limit Exceeded

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

n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
s=sum(arr)
ans=1
d=div(s)
for val in d:
  arr=sorted(arr,key=lambda x:x%val)
  for i in range(n-1):
    pcnt=0
    ncnt=0
    for j in range(n):
      if j<=i:
        ncnt+=arr[j]%val
      else:
        pcnt+=(val-arr[j]%val)
    if ncnt!=pcnt:
      continue
    else:
      if pcnt<=k:
        ans=max(ans,val)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
total = sum(a)
divisor = []
for i in range(int(total ** 0.5)):
    if total % (i + 1) == 0:
        divisor.append(i + 1)
        divisor.append(total // (i + 1))
divisor.sort(reverse = True)
i = 0
while True:
    num = divisor[i]
    a2 = [a[j] % num for j in range(n)]
    count = 0
    res = 0
    while a2:
        test = min(a2)
        a2.remove(test)
        count += test
        res += test
        while res:
            test2 = max(a2)
            if res >= num - test2:
                res -= num - test2
                a2.remove(test2)
            else:
                a2[a2.index(test2)] += res
                res = 0
    if count <= k:
        break
    else:
        i += 1
print(num)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
def divisor_list(N): #素因数分解
    res = []
    i = 1
    while i*i < N:
        if N%i == 0:
            res.append(i)
            res.append(N//i)
        i += 1
    if i*i == N: res.append(i)
    return sorted(res)

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,k = [int(i) for i in readline().split()]
a = [int(i) for i in readline().split()]


l = reversed(divisor_list(sum(a)))


def check(x):
    res = []
    for ai in a:
        c = ai%x
        d = ai%x-x
        if abs(c) > abs(d): res.append(d)
        else: res.append(c)
    res.sort(key = abs)
    
    d = sum(res)

    if d > 0:
        idx = -1
        while d != 0:
            if res[idx]>0:
                d -= x
                res[idx] -= x
                idx -= 1
    if d < 0:
        idx = -1
        while d != 0:
            if res[idx]<0:
                d += x
                res[idx] += x
                idx -= 1
                
    c = sum([x for x in res if x > 0])        

#    print(x,c,res)
    return (c <= k)



for x in l:
    if check(x):
        print(x)
        exit()

Submission status: Time Limit Exceeded

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

A.sort(reverse=True)
p = sum(A)
flag = 0
for i in range(N-1):
    if K >= p - sum(A[:i+1]):
        p//=(i+1)
        flag=1
        break

if flag == 0:
    p //= N

while p > 0:
    z = 0
    for i in range(N):
        z += A[i] % p
    if z % p == 0:
        B = [i % p for i in A]
        B.sort(reverse=True)
        q = z//p
        j = 0
        for i in range(q):
            j += p-B[i]
        if K >= j:
            print(p)
            exit()
    p -= 1

print(p)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

def part_sum(a,A):
  N=len(a)
  dp=[[0 for i in range(A+1)] for j in range(N+1)]
  dp[0][0]=1

  for i in range(N):
    for j in range(A+1):
      if a[i]<=j: 
        dp[i+1][j]=dp[i][j-a[i]] or dp[i][j]
      else: 
        dp[i+1][j]=dp[i][j]
  return dp[N][A]

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

s=sum(a)
s_factors=[]

l=int(math.sqrt(s))

for i in range(1,l+1):
    if s%i==0:
        s_factors.append(i)
        s_factors.append(s//i)

s_factors.sort()

for f in s_factors[::-1]:
    b=[a[i]%f for i in range(n)]
    c=[f-a[i]%f for i in range(n)]
    
    b.sort()
    c.sort()
    c=c[::-1]

    for i in range(n):
        if sum(b[:i+1])==sum(c[i+1:]):
            if sum(b[:i+1])<=k:
                print(f)
                sys.exit()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque


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


def can_divide_by(mod, N, K, A):
    mod_a = [a % mod for a in A if a % mod != 0]
    if sum(mod_a) % mod != 0:
        False

    mod_a.sort()
    dq = deque(mod_a)
    op = K
    while len(dq) > 0 and op > 0:
        l = dq.popleft()
        r = dq.pop()
        l -= 1
        r += 1
        if l % mod != 0:
            dq.appendleft(l)
        if r % mod != 0:
            dq.append(r)
        op -= 1

    return len(dq) == 0


def divisors(x):
    res = []
    for i in range(1, x + 1):
        if x % i == 0:
            res.append(i)
            if i**2 != x:
                res.append(x // i)
        if i ** 2 >= x:
            break
    return sorted(res, reverse=True)


def solve(N: int, K: int, A: "List[int]"):
    for mod in divisors(sum(A)):
        if can_divide_by(mod, N, K, A):
            return mod


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    ans = solve(N, K, A)
    if ans is not None:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

sa = sum(A)
m = 1
divs = set()
while m*m <= sa:
    if sa%m == 0:
        divs.add(m)
        divs.add(sa//m)
    m += 1

for d in sorted(divs,reverse=True):
    mods = []
    for a in A:
        mods.append(a%d)
    mods.sort()
    if all(m==0 for m in mods):
        print(d)
        exit()
    for i in range(N-1):
        plus = minus = 0
        for j,m in enumerate(mods):
            if j <= i:
                plus += m
            else:
                minus += d-m
        if plus == minus and plus <= K:
            print(d)
            exit()

Submission status: Time Limit Exceeded

Solution code:
words = lambda t : list(map(t, input().split()))
n,k = words(int)
xs = words(int)

def divisor (x):
    ans = [1]
    for i in range(2, x//2+1):
        if x % i == 0:
            ans.append(i)
    ans.append(x)
    return list(reversed(ans))

s = sum(xs)
ds = divisor(s)
ans = 1
#print(ds)
for d in ds:
    ms = []
    for x in xs:
        ms.append(x%d)
    ms.sort()
    #print(d,ms)
    f = 0
    f_ttl = ms[f]
    b = len(ms)-1
    b_ttl = d - ms[b]
    while f != b:
        if f_ttl >= b_ttl:
            b -= 1
            b_ttl += d - ms[b]
        else:
            f += 1
            f_ttl += ms[f]
    if k >= f_ttl:
        ans = d
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque


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


def can_divide_by(mod, N, K, A):
    mod_a = [a % mod for a in A if a % mod != 0]
    if sum(mod_a) % mod != 0:
        False

    mod_a.sort()
    dq = deque(mod_a)
    op = K
    while len(dq) > 0 and op > 0:
        l = dq.popleft()
        r = dq.pop()
        l -= 1
        r += 1
        if l % mod != 0:
            dq.appendleft(l)
        if r % mod != 0:
            dq.append(r)
        op -= 1

    return len(dq) == 0


def dividers(x):
    for i in range(x, 0, -1):
        if x % i == 0:
            yield i


def solve(N: int, K: int, A: "List[int]"):
    for mod in dividers(sum(A)):
        if can_divide_by(mod, N, K, A):
            return mod


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    ans = solve(N, K, A)
    if ans is not None:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# E

import sys

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

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

s = sum(a)

for p in range(1,s+1) :
    if s % p != 0:
        continue
    b = s // p
    
    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)

Submission status: Time Limit Exceeded

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

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

x=sum(A)
import math
xr=math.ceil(math.sqrt(x))

LIST=[]
for i in range(1,xr+1):
    if x%i==0:
        LIST.append(i)
        LIST.append(x//i)


MIN=0
MAX=sum(A)
ANS=1
A.sort()

for l in LIST:
    count=0

    B=[a%l for a in A]
    B.sort()

    i=0
    j=N-1

    for i in range(N):
        if B[i]%l==0:
            continue
        else:
            count_temp=0
            while B[i]%l!=0:
                B[i]-=1
                count_temp+=1

            for t in range(count_temp):
                while B[j]%l==0:
                    j-=1
                B[j]+=1

        count+=count_temp


    if count<=K:
        ANS=max(ANS,l)

print(ANS)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
*A, = map(int, input().split())
A.sort()

def chk(x):
    D = []
    c = 0
    for a in A:
        y = a % x
        D.append(y)
    D.sort()
    s = sum(D)
    e = 0; r = N*x - s
    for d in D:
        e += d
        r -= x - d
        if e == r and e <= K:
            return 1
    return 0

ans = 1
S = sum(A)
for x in range(2, S+1):
    if S % x == 0:
        if chk(x):
            ans = x
print(ans)