Problem:


Score : 200 points

Problem Statement

There are K pieces of cakes.
Mr. Takahashi would like to eat one cake per day, taking K days to eat them all.

There are T types of cake, and the number of the cakes of type i (1 ≤ i ≤ T) is a_i.  

Eating the same type of cake two days in a row would be no fun,
so Mr. Takahashi would like to decide the order for eating cakes that minimizes the number of days on which he has to eat the same type of cake as the day before.  

Compute the minimum number of days on which the same type of cake as the previous day will be eaten.

Constraints

1 ≤ K ≤ 10000

1 ≤ T ≤ 100

1 ≤ a_i ≤ 100

a_1 + a_2 + ... + a_T = K

Input

The input is given from Standard Input in the following format:

K T
a_1 a_2 ... a_T

Output

Print the minimum number of days on which the same type of cake as the previous day will be eaten.

Sample Input 1

7 3
3 2 2

Sample Output 1

0

For example, if Mr. Takahashi eats cakes in the order of 2, 1, 2, 3, 1, 3, 1, he can avoid eating the same type of cake as the previous day.

Sample Input 2

6 3
1 4 1

Sample Output 2

1

There are 6 cakes.
For example, if Mr. Takahashi eats cakes in the order of 2, 3, 2, 2, 1, 2, he has to eat the same type of cake (i.e., type 2) as the previous day only on the fourth day.
Since this is the minimum number, the answer is 1.

Sample Input 3

100 1
100

Sample Output 3

99

Since Mr. Takahashi has only one type of cake, he has no choice but to eat the same type of cake as the previous day from the second day and after.



Sample input:
7 3
3 2 2


Sample output:
0

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
other = sum(A)-max(A)
if max(A)-1>other:
  ans = max(A)-1-other

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    k, t = LI()
    a = LI()
    dp = [0] * (k + 1)
    l = r = 0
    dp[0] = 1
    for ai in a:
        for i in range(k, ai - 1, -1):
            dp[i] |= dp[i - ai]
    ans = inf
    for i in range(k + 1):
        if dp[i]:
            ans = min(ans, max(k - i - i, i - (k - i)))
    if ans:
        print(ans - 1)
    else:
        print(0)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = list(map(int, input().split()))
Q = list(map(int, input().split()))
maxQ = max(Q)
rest = N[0] - maxQ
print(max([maxQ-rest-1, 0]))

Submission status: Accepted

Solution code:
import sys

k,n=map(int,input().split())
a=list(map(int,input().split()))
if n==1: print(a[0]-1);sys.exit()

a.sort(reverse=True)
ans=max(0,a[0]-1-sum(a[1:]))
print(ans)

Submission status: Accepted

Solution code:
import sys

k,n=map(int,input().split())
a=list(map(int,input().split()))
a=[[a[i],i] for i in range(n)]

if n==1: print(a[0][0]-1);sys.exit()

pre=-1
ans=0
for _ in range(k):
    a.sort(reverse=True)
    if a[0][1]!=pre:
        a[0][0]-=1
        pre=a[0][1]
    elif a[1][0]>0:
        a[1][0]-=1
        pre=a[1][1]
    else:
        ans=a[0][0]
        break
print(ans)

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
A = list(map(int, input().split()))
res = K - max(A)
a = max(A)
if T == 1:
    print(K - 1)
    exit()
if res >= a + 1:
    print(0)
    exit()

ans = a - 1
ans -= res
print(ans)

Submission status: Accepted

Solution code:
def main():
    cakes, variation = map(int, input().split())
    cake_num = list(map(int, input().split()))
    cake_num.sort()
    print(max(0, 2 * cake_num[-1] - cakes - 1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

def solve():
  k, t = list(map(int, input().split()))
  a = list(map(int, input().split()))
  
  q = []
  
  for i in range(len(a)):
    if a[i] != 0:
      heapq.heappush(q, (-a[i], i))
  
  count, i = heapq.heappop(q)
  count += 1
  keep = (count, i)

  while len(q) > 0:
    count, i = heapq.heappop(q)
    count += 1
    
    if keep[0] < 0:
      heapq.heappush(q, keep)
    keep = (count, i)
  
  print(- keep[0])
  return

if __name__ == "__main__":
  solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
k,t = map(int,input().split())	
a = list(map(int,input().split()))
print(max(0,2*(max(a)-(k+1)//2)-1))

Submission status: Accepted

Solution code:
k,t=map(int,input().split())
a=list(map(int,input().split()))
m=max(a)
n=k-m
print(max(m-n-1,0))

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
a = list(map(int, input().split()))

mx = max(a)
ans = max(mx - 1 - (k - mx), 0)
print(ans)

Submission status: Accepted

Solution code:
import heapq

K, T = map(int, input().split())
a = [int(i) for i in input().split()]
b = [[0 for j in range(2)] for i in range(T)]
for i in range(T):
	b[i][0] = a[i] * -1
	b[i][1] = i
heapq.heapify(b)
ans, c = 0, -1
while len(b):
	d = heapq.heappop(b)
	if c == d[1]:
		if not len(b):
			ans += 1
			c = d[1]
			d[0] += 1
			if d[0]:
				heapq.heappush(b, d)
		else:
			e = heapq.heappop(b)
			c = e[1]
			e[0] += 1
			heapq.heappush(b, d)
			if e[0]:
				heapq.heappush(b, e)
	else:
		c = d[1]
		d[0] += 1
		if d[0]:
			heapq.heappush(b, d)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(K: int, T: int, a: "List[int]"):
    from heapq import heapify, heappop, heappush

    a = list(map(lambda x:x*(-1), a))
    heapify(a)
    while True:
        if len(a) <= 1:
            break

        x = -1*heappop(a)
        y = -1*heappop(a)
        x -= 1
        y -= 1
        if x > 0:
            heappush(a, -x)
        if y > 0:
            heappush(a, -y)

    if len(a) == 1:
        print(-1*a[0]-1)
    else:
        print(0)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(T) ]  # type: "List[int]"
    solve(K, T, a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

mx = max(a)

if k -mx >= mx -1:
    print(0)
else:
    print(2*mx-k-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
K, T = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
A = [(-a, i) for i, a in enumerate(A)]

import heapq
heapq.heapify(A)

prev = -1
while len(A) > 1:
    a, i = heapq.heappop(A)
    if i == prev:
        b, j = heapq.heappop(A)
        prev = j

        heapq.heappush(A, (a, i))
        b += 1
        if b != 0:
            heapq.heappush(A, (b, j))

    else:
        prev = i
        a += 1
        if a != 0:
            heapq.heappush(A, (a, i))



print(- A[0][0] - 1)

Submission status: Accepted

Solution code:
k,t = map(int, input().split())
a = [int(s) for s in input().split()]

if max(a) <= k / 2:
  print(0)
else:
  print(k - 2*(k-max(a)) - 1)

Submission status: Accepted

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

MX = max(A)

if K-MX >= MX-1:
    print(0)
else:
    print(2*MX-K-1)

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def can_set(al_max ,k,cc):
	a=al_max
	aa=((k//(cc+1))*cc) + (k%(cc+1))
	#pa((a,cc,aa))
	if a <= aa:
		return True
	return False

def main():
	k, t = IN()
	al = list(IN())
	al.sort(reverse=True)
	#pa(al)
	
	#if al[0] <= (k+1)//2:
	#	return 0
	#if al[0] == k:
	#	return k-1
	tt=sum(al)
	mm=al[0]
	nokori=tt-mm
	ret = max(0, tt - nokori*2-1)
	print(ret)
	
	

def main2():
	k, t = IN()
	al = list(IN())
	al.sort(reverse=True)
	ttt=[0]*k
	p=0
	for i, v in enumerate(al):
		for _ in range(v):
			ttt[p]=i
			p+=2
			if p >= k:
				p=1
	
	cc=0
	pre=-1
	for v in ttt:
		if pre == v:
			cc+=1
		else:
			pre=v
			
	return cc
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
from bisect import bisect_left
def main():
    k, t = map(int, input().split())
    a = list(map(int, input().split()))
    ans = 0
    pre = -1
    a.sort()
    for _ in range(k):
        x = bisect_left(a, a[t-1])
        if x == pre:
            if t > 1 and a[x-1] > 0:
                x = bisect_left(a, a[x-1])
            else:
                ans += 1
        a[x] -= 1
        pre = x
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    K,T = map(int,input().split())
    A = list(map(int,input().split()))
    ans = 0
    for i in range(T):
        ans = max(ans,2*A[i]-1-K)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
alist = sorted(list(map(int, input().split())))[::-1]
alist.append(0)
print(max(0, alist[0]-sum(alist[1:])-1))

Submission status: Accepted

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

A.sort()
if T == 1:
    print(A[0] - 1)
else:
    print(max(0, A[-1] - (K - A[-1] + 1)))

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
amax = a[-1]
asum = sum(a[:-1])
ans = 0
if T == 1:
    ans = K - 1
else:
    ans = max(amax - asum - 1, 0)
print(ans)

Submission status: Accepted

Solution code:
k,t=map(int,input().split())
print(max(0,2*max(list(map(int,input().split())))-k-1))

Submission status: Accepted

Solution code:
K,T=map(int,input().split())
A=list(map(int,input().split()))
if K%2==0:
  a=K//2
  b=max(A)
  if a>=b:
    print(0)
  else:
    print((b-a)*2-1)
else:
  a=K//2+1
  b=max(A)
  if a>=b:
    print(0)
  else:
    print((b-a)*2)

Submission status: Accepted

Solution code:
k,t=map(int,input().split())
a=list(map(int,input().split()))
ans=max(2*max(a)-sum(a)-1,0)
print(ans)

Submission status: Accepted

Solution code:
# K個のケーキ
k,t=map(int,input().split())
a=list(map(int,input().split()))

m=max(a)
print(max(m-1-(k-m),0))

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
while len(a) > 1:
    a[-1] -= 1
    a[-2] -= 1
    if a[-1] == 0:
        a.pop(-1)
        if a[-1] == 0:
            a.pop(-1)
    else:
        if a[-2] == 0:
            a.pop(-2)
    a.sort()
if len(a) == 1:
    print(a[0]-1)
else:
    print(0)

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
alist = sorted(list(map(int, input().split())))
m = alist[-1]
other_sum = sum(alist)-m
print(max(m-other_sum-1, 0))

Submission status: Accepted

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

def main():
    K,T = map(int,input().split())
    a = list(map(int,input().split()))
    
    between = max(a)-1
    use = sum(a)-max(a)

    print(max(0,between-use))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
K,T,*A=map(int, open(0).read().split())
ma=max(A)
sa=sum(A)
ans=max(0,ma-(sa-ma)-1)
print(ans)

Submission status: Accepted

Solution code:
k,t = map(int,input().split())
A = list(map(int,input().split()))
print(max(0,2*max(A) - sum(A) -1))

Submission status: Accepted

Solution code:
k,t=map(int,input().split())
a=list(map(int,input().split()))
print(max((2*max(a)-1-k),0))

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
A = [int(a) for a in input().split()]
M = max(A)
print(max(2 * M - K - 1, 0))

Submission status: Accepted

Solution code:

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

A.sort()
summation = sum(A[:-1])
maximum = A[-1]

#print(f'{maximum=} {summation=}')
if summation > maximum-2:
    print(0)
else:
    if summation != 0:
        ans = maximum-summation
        print('{}'.format(ans-1))
    else:
        print('{}'.format(maximum-1))

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
A = sorted(list(map(int, input().split())))

if t == 1:
    print(k-1)
elif A[-1] > k/2:
    print(A[-1] - sum(A[:-1]) - 1)
else:
    print(0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

k, t = [int(x) for x in input().split()]
a = sorted([int(x) for x in input().split()], reverse=True)
s = a.pop(0) - 1
for e in a:
    s -= e
print(s if s > 0 else 0)

Submission status: Accepted

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


def main():
    K,T,*a = map(int, read().split())

    a.sort()
    ans = max(a[-1] - 1 - (K-a[-1]), 0)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
a = list(map(int, input().split()))
m_a = max(a)
s_a = sum(a)-max(a)

print(m_a - (s_a+1) if m_a > (s_a+1) else 0)

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
a = list(map(int, input().split()))
max_a = max(a)
others = k-max_a
print(max(max_a - 1 - others, 0))

Submission status: Accepted

Solution code:
K, T = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort(reverse=True)
if T > 1:
    n = a[0]-a[1]
else:
    print(a[0]-1)
    exit()
for i in range(2, T):
    n = abs(n-a[i])
print(max(0, n-1))

Submission status: Accepted

Solution code:
k,t = list(map(int,input().split())) 
a = list(map(int,input().split())) 

if max(a)<=(sum(a)-max(a)):
    print(0)
else:
    print(max(a)-1-(sum(a)-max(a)))

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
ma = max(list(map(int, input().split())))
print(max(0, ma - 1 - (k - ma)))

Submission status: Accepted

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

ans = max(0,max(A)*2-sum(A)-1)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
K, T = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
print(max(A[-1] - 1 - (K - A[-1]), 0))

Submission status: Accepted

Solution code:
# coding: utf-8
K, T = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
B = A[:]
tmp = 0
for i in range(T-1):
    minus = B[i]
    for j in range(i, T):
        A[j] -= minus
#     print(*A)
# print(*A)

ans = 0
for i in range(T):
    if A[i] > 0:
        ans += A[i] - 1
print(ans)

Submission status: Accepted

Solution code:
k, t = list(map(int, input().split()))
a = list(map(int, input().split()))
m = max(a)
print(max(2*m-k-1, 0))

Submission status: Accepted

Solution code:
K,T = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=1)
if a[0] <= (K+1)//2:
    print(0)
else:
    print(2*a[0] - K-1)

Submission status: Accepted

Solution code:
K, T = map(int, input().split())

A = list(map(int, input().split()))
m = max(A)

print(max(0, m - 1 - (K - m)))

Submission status: Accepted

Solution code:
import heapq
K, T = map(int, input().split())
L = list(map(lambda x: -int(x), input().split()))

heapq.heapify(L)

while L and len(L) > 1:
    a = heapq.heappop(L)
    b = heapq.heappop(L)
    r = b-a
    if r > 0:
        heapq.heappush(L, -r)
if L:
    print(-heapq.heappop(L)-1)
else:
    print(0)

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
a = sorted(list(map(int, input().split())))

b = a.pop()
print(max(0,b-sum(a)-1))

Submission status: Accepted

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

A.sort()
print(max(0, A[-1] - 1 - (K - A[-1])))

Submission status: Accepted

Solution code:
import sys

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

tot = sum(A)

for i in range(T):
	if A[i] > -(-tot//2):
		print(A[i]-(tot-A[i]+1))
		sys.exit()

print(0)

Submission status: Accepted

Solution code:
k,t = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
a.reverse()

first = a[0]
rest  = k-a[0]

ans = first-rest-1
if ans < 0:
        print(0)
else:
        print(ans)

Submission status: Accepted

Solution code:
k,t=map(int,input().split())
a=list(map(int,input().split()))
# 前回と同じケーキ以外でそのとき最も残り個数が多いものを常に入れていく。
# 前回と同じケーキしか残っていなければそれを入れる。

if t==1:
  print(k-1)
  exit(0)

cakes=[0]*t
for i in range(len(a)):
  cakes[i]=[a[i],i]

cur=-1
ans=0
for i in range(k):
  cakes=sorted(cakes,key=lambda x:x[0])
  if cakes[-1][1]!=cur:
    cakes[-1][0]-=1
    cur=cakes[-1][1]
  else:
    if cakes[-2][0]==0:
      cakes[-1][0]-=1
      cur=cakes[-1][1]
      ans+=1
    else:
      cakes[-2][0]-=1
      cur=cakes[-2][1]
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
k,t = [int(x) for x in stdin.readline().rstrip().split()]
li = list(map(int,stdin.readline().rstrip().split()))
print(max(0,max(li)-1-(k-max(li))))

Submission status: Accepted

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

ans = 0
for a in A:
    if a > (K + 1) // 2:
        ans += 2 * (a - (K + 1) // 2) - 1


print (ans)

Submission status: Accepted

Solution code:
input()
a=list(map(int,input().split()))
print(max(0,max(a)*2-sum(a)-1))

Submission status: Accepted

Solution code:
input().split()
a = list(map(int,input().split()))
print(max(0,max(a)*2-sum(a)-1))

Submission status: Accepted

Solution code:
def main():
    K, T = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    if T == 1:
        print(A[0] - 1)
    else:
        A.sort()
        print(max(A[-1] - sum(A[:-1]) - 1, 0))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    K, T = MI()
    A= LI()
    A_max = max(A)
    others  = K - A_max
    if A_max < ceil(K,2):
        print(0)
    else:
        print(A_max - 1 - others)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
print(max(0, a[-1] - sum(a[:-1]) - 1))

Submission status: Accepted

Solution code:
k,t = map(int,input().split())
al = list(map(int,input().split()))

al = sorted(al)

print(max(2 * max(al) - k - 1, 0))

Submission status: Accepted

Solution code:
k,t = map(int,input().split())
lst = list(map(int,input().split()))

mx = max(lst)
print(max(0,mx-1-(k-mx)))

Submission status: Accepted

Solution code:
import heapq

k,t=map(int,input().split())
a=list(map(int,input().split()))
a=list(map(lambda x: -1*x,a))
heapq.heapify(a)

h=heapq.heappop(a)
h+=1
pre_h=h

while(len(a)>0):
    h=heapq.heappop(a)
    if(h==0):
        break
    else:
        h+=1
        heapq.heappush(a, pre_h)
        pre_h=h

print(-1*pre_h)

Submission status: Accepted

Solution code:
k,t = map(int,input().split())
lst1 = list(map(int,input().split()))

if t == 1:
    print(lst1[0]-1)

elif max(lst1) - (sum(lst1) - max(lst1)) > 0:
    print(max(lst1) - (sum(lst1) - max(lst1))-1)

else:
    print(0)

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
a = list(map(int, input().split()))
mxa = max(a)
ans = max(mxa-1-(K-mxa), 0)
print(ans)

Submission status: Accepted

Solution code:
k,t = map(int,input().split())
a = [int(i) for i in input().split()]
print(max(0,2*max(a)-k-1))

Submission status: Accepted

Solution code:
K,T = map(int,input().split())
a = list(map(int,input().split()))
a = sorted(a,reverse=True)
print(max(0,a[0] -sum(a[1:]) -1))

Submission status: Accepted

Solution code:



import heapq

K,T = map(int, input().split())

A = list(map(int, input().split()))
if T == 1:
    print(K-1)
    exit()

q = []
for i in range(len(A)):
    heapq.heappush(q, -1*A[i])


while len(q) > 1:
    x = heapq.heappop(q)
    y = heapq.heappop(q)
    heapq.heappush(q, x-y)

print(max(0, -q[0]-1))

Submission status: Accepted

Solution code:
# 解説を見た

k, t = map(int, input().split())
*a, = (int(x) for x in input().split())

ma = max(a)
rest = k - ma
print(max(0, ma - rest - 1))

# 最大の個数のケーキを並べる
# 間にほかのケーキを挟んでいく
# aaaaaa bbbb ccc d
# a[bc]a[bc]a[bc]a[b]a[d]a
# 間に1個ずつ入れたときの、aが連続する回数-1が答え
# 間に複数入ることはあるが、同じケーキが入ることはない（最大のケーキの間の数は、ほかのどのケーキの個数よりも多いから）

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

k, t = map(int, input().split())
*a, = (-int(x) for x in input().split())

heapify(a)

eaten = 0
while a:
    to_eat = heappop(a)
    to_eat += 1
    if eaten:
        heappush(a, eaten)
        eaten = 0
    if to_eat == 0:
        continue
    elif to_eat < 0:
        eaten = to_eat

print(-eaten)

Submission status: Accepted

Solution code:
from heapq import *
import bisect

k,t=map(int,input().split())
a=sorted([-int(i) for i in input().split()],reverse=True)

heapify(a)
while len(a)>=2:
 max=heappop(a)
 min=a.pop(-1)
 if max+1<=-1:
  bisect.insort(a,max+1)
 if min+1<=-1:
  heappush(a,min+1)
if a:
 print(abs(a[0]+1))
else:
 print(0)

Submission status: Accepted

Solution code:
import heapq
import bisect

k,t=map(int,input().split())
a=sorted([-int(i) for i in input().split()],reverse=True)

heapq.heapify(a)
while len(a)>=2:
 max=heapq.heappop(a)
 min=a.pop(-1)
 if max+1<=-1:
  bisect.insort(a,max+1)
 if min+1<=-1:
  heapq.heappush(a,min+1)
if a:
 print(abs(a[0]+1))
else:
 print(0)

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
a = list(map(int, input().split()))

print(max(0, (max(a) - (K // 2 + K % 2)) * 2 - (1 - K % 2)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
k, t = map(int,input().split())
A = list(map(int,input().split()))

A.sort(reverse=True)
if t == 1:
    print(A[0] - 1)
else:
    a = A[0]
    b = sum(A[1:])
    print(max(0,a-b-1))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial, ceil, floor
from collections import defaultdict
import itertools
sys.setrecursionlimit(200000)
input = sys.stdin.readline

# N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

K, T, = map(int, input().split())
L = [int(v) for v in input().split()]

for i in range(T):
    L[i] = (-L[i], i)

heapify(L)

m = [None] * K
index = 0
before = None
for _ in range(K):
    if len(L) == 0:
        heappush(L, before)
        before = None

    a, b = heappop(L)
    if before != None:
        heappush(L, before)
        before = None

    m[index] = b
    index += 1
    if a + 1 != 0:
        before = (a + 1, b)

if before != None:
    a, b = before
    m[-1] = b

ans = 0
for i in range(K - 1):
    if m[i] == m[i + 1]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import heapq
def main():
    K,T = map(int,input().split())
    A = [-int(x) for x in input().split()]
    if T == 1:
        print(K-1)
        exit()

    heapq.heapify(A)
    first = heapq.heappop(A)
    while 1:
        second = heapq.heappop(A)
        if second==0:
            break
        else:
            heapq.heappush(A,first+1)
            first = second
    print(-first-1)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
A = list(map(int, input().split()))
maxa = max(A)
print(2*maxa - K - 1 if 2*maxa - K - 1 > 0 else 0)

Submission status: Accepted

Solution code:
k,t=map(int,input().split())
a=list(map(int,input().split()))
print(max(0,max(a)-(k-max(a))-1))

Submission status: Accepted

Solution code:
k,t = map(int, input().split())
a = list(map(int, input().split()))
b = max(a)
s = sum(a)
s -=b
ans = max(b-s-1,0)
print(ans)

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
A = [int(a) for a in input().split()]
A.sort()
sumA = 0
for a in A[:T-1]: sumA += a
print(max(0, A[T-1] - 1 - sumA))

Submission status: Accepted

Solution code:
K,T = map(int,input().split())
A = list(map(int,input().split()))
ma = max(A)
print(max(ma-(K-ma)-1,0))

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
cnt = 0
if T == 1:
    print(K - 1)
    exit()

tmp = a[0] - sum(a[1:])
if tmp <= 0:
    print(0)
else:
    print(tmp - 1)

Submission status: Accepted

Solution code:

K,T = map(int,input().split())

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

a.sort()

if a[-1] * 2 <= (sum(a) - a[-1]) * 2  + 2:
    print (0)

else:
    print (a[-1] - (sum(a) - a[-1] + 1 ))

Submission status: Accepted

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))
import sys
input = sys.stdin.readline

K, T = two_int()

A=many_int()

A = sorted(A)

maxs = A[-1]
other = sum(A[:-1])

if maxs <= other:
    print(0)
else:
    print(maxs-other-1)

Submission status: Accepted

Solution code:
k,t =map(int,input().split())
l = list(map(int,input().split()))

if max(l)-(sum(l)-max(l))>=2:
	print(max(l)-(sum(l)-max(l))-1)
else:
	print(0)

Submission status: Accepted

Solution code:
k,t=map(int,input().split())
a = list(map(int,input().split()))
mx = max(a)
print(max(0,(mx-(k+1)//2)*2-1))

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
a = list(map(int, input().split()))
cnt = [0] * t
for i in range(t):
    cnt[i] += sum(a[:i])
    if i != t - 1:
        cnt[i] += sum(a[i + 1:])
ans = -1
for i in range(t):
    if a[i] > cnt[i]:
        ans += a[i] - cnt[i]
print(max(ans, 0))

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
A = list(map(int, input().split()))
print(max(0, max(A)-1-(K-max(A))))

Submission status: Accepted

Solution code:
K,T = map(int,input().split())
A = list(map(int,input().split()))
maxA = max(A)
print(0 if maxA<=K//2+K%2 else 2*(maxA-(K//2+K%2))-1)

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
A = [int(a) for a in input().split()]
print(max(max(A) * 2 - 1 - K, 0))

Submission status: Accepted

Solution code:
K,T = map(int,input().split())
A = sorted(list(map(int,input().split())))
a = A.pop()
for i in range(1,T):
    a = abs(a-A.pop())
    A = sorted(A)
if a==0:
    cnt = a
else:
    cnt = a-1
print(cnt)

Submission status: Accepted

Solution code:
import heapq


def m():
    K, T = [int(x) for x in input().split(' ')]
    A = [int(x) for x in input().split(' ')]
    h = sorted([-x for x in A])

    tmp = 0
    suc = 0
    while len(h) > 0:
        suc += 1
        a = heapq.heappop(h)
        if tmp < 0:
            heapq.heappush(h, tmp)
        tmp = a + 1
    print(K - suc)


m()

Submission status: Accepted

Solution code:
import sys
import bisect
k, t = [int(i) for i in sys.stdin.readline().split()]
a_ls = [int(i) for i in sys.stdin.readline().split()]
sum_a = sum(a_ls)
memo_ls = [[0 for i in range(k+1)]for j in range(t+1)]
memo_ls[0][0] = 1
for i, cake in enumerate(a_ls, 1):
    for j in range(k+1):
        memo_ls[i][j] = memo_ls[i-1][j]
        if j >= cake:
            memo_ls[i][j] = max(memo_ls[i-1][j-cake], memo_ls[i][j])

ls = [i for i, j in enumerate(memo_ls[-1]) if j > 0]
ind = bisect.bisect_left(ls, sum_a / 2)
if ls[ind] == sum_a // 2:
    print(0)
else:
    print(max(ls[ind] - ls[ind - 1] - 1, 0))

Submission status: Accepted

Solution code:
K,T = map(int,input().split())
A = list(map(int,input().split()))
print(max((max(A)-K//2)*2-1-K%2,0))

Submission status: Accepted

Solution code:
k,t = map(int,input().split())
a = max(map(int,input().split()))
print(max(0,2*a-k-1))

Submission status: Accepted

Solution code:
k,t = map(int,input().split())
a = list(map(int,input().split()))

max = max(a)

if 2 * max - 1 <= k:
    ans = 0
else:
    ans = 2 * max - 1 - k
print(ans)

Submission status: Accepted

Solution code:
def examA():
    S = SI()
    ans = "No"
    flag = False
    for s in S:
        if flag:
            if s=="F":
                ans = "Yes"
                break
        else:
            if s=="C":
                flag = True
    print(ans)
    return

def examB():
    K, T = LI()
    A = LI(); A.sort()
    ans = max(0,A[-1]*2-sum(A)-1)
    print(ans)
    return


import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examB()