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:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    K, T = MI()
    A = LI()

    if T == 1:
        print(A[0] - 1)
        return

    A = sorted(A, reverse=True)
    mx1, mx2 = A[0], A[1]
    if mx1 == mx2:
        print(0)
        return
    else:
        ans = max(0, mx1 - 1 - sum(A[1:]))
        print(ans)
        return

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    K,T=MI()
    a=LI()
    M=max(a)
    if M<=(K+1)//2:
        print(0)
    else:
        temp=sum(a)-M
        ans=M-temp-1
        print(ans)
        

main()

Submission status: Accepted

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

ans = (A[-1] - 1) - (K-A[-1])
print(max(ans, 0))

Submission status: Accepted

Solution code:
k,t = map(int,input().split())
a = list(map(int,input().split()))
b = [0]*t
for i in range(t):
    b[i] = [a[i], i]
s = -1
ans = 0
if t == 1:
    ans = k-1
else:
    for i in range(k):
        b.sort(key= lambda val : val[0],reverse=True)
        if b[0][1] == s:
            if b[1][0] == 0:
                ans = b[0][0]
                break
            else:
                b[1][0] -= 1
                s = b[1][1]
        else:
            b[0][0] -= 1
            s = b[0][1]
print(ans)

Submission status: Accepted

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

max1 = max(L)
zan = k-max1

print(max(0,(max1-1)-zan))

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
a_list = [[int(value), index] for index, value in enumerate(input().split())]
ans = 0
prev = -1
for i in range(k):
    a_list.sort(reverse=True)
    index = 0
    if prev == a_list[index][1]:
        if len(a_list) > 1:
            index += 1
        else:
            ans += 1
    prev = a_list[index][1]
    if a_list[index][0] == 1:
        a_list.pop(index)
    else:
        a_list[index][0] -= 1
print(ans)

Submission status: Accepted

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

maxix = 0
maxv = -1

for aix in range(T):
    if A[aix] > maxv:
        maxv = A[aix]
        maxix = aix

total = 0
for aix in range(T):
    if aix == maxix:
        continue
    else:
        total += A[aix]

if maxv - 1 > total:
    print(maxv-total-1)
else:
    print(0)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

k, t = MAP()
a = LIST()

ans = max(0, ( max(a) - (k+1)//2 ) * 2 - 1)
print(ans)

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
max_value = A[-1]
others = sum(A[:-1])
print(max(0, max_value - others - 1))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k,t,*aa = map(int, open(0).read().split())
aa.sort(reverse=True)

eligible = min(aa[0], sum(aa[1:]) + 1) + sum(aa[1:])

print(k-min(k,eligible))

Submission status: Accepted

Solution code:
import sys
k,t,*aa = map(int, open(0).read().split())
aa.sort(reverse=True)

eligible = min(aa[0], sum(aa[1:]) + 1) + sum(aa[1:])

print(k-min(k,eligible))

Submission status: Accepted

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

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

def main():
    K, T = MII()
    A = LII()

    A.sort()
    cnt = A[-1] - sum(A[:-1]) - 1
    print(cnt if cnt > 0 else 0)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

max_a = max(A)
print(max(0, max_a-1-(K-max_a)))

Submission status: Accepted

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

if T == 1:
    print(A[0]-1)
    exit()
su = sum(A[1:])
if A[0] - su >= 2:
    print(A[0] - su - 1)
else:
    print(0)

Submission status: Accepted

Solution code:
k,t=map(int,input().split())
a=list(map(int,input().split()))
ma=max(a)
if ma >= sum(a)-ma+1:
  print(ma-(sum(a)-ma)-1)
else:
  print(0)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    K, T = in_nn()
    a = in_nl()
    maxA = max(a)
    mT = -(-K // 2)
    ans = max(0, (maxA - mT) * 2 - 1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


inf = 10 ** 18
mod = 10 ** 9 + 7

k,t = lr()
a = lr()
maxa = max(a)
if maxa > (k+1)//2:
    print((maxa-((k+1)//2))*2-1)
else:
    print(0)

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
A = list(map(int, input().split()))
if t == 1:
    print(k-1)
else:
    maxi = 0
    for i in range(t):
        maxi = max(maxi, i, key=lambda x:A[x])
    maxa = A.pop(maxi)
    sa = sum(A)
    print(max(0, maxa-1 - sa))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
alst = list(map(int, input().split()))
total = sum(alst)
max_num = max(alst)

print(max(0, max_num * 2 - total - 1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
A = list(map(int, input().split()))
if max(A) < k//2+1:
    print(0)
else:
    print(max(A)-(sum(A)-max(A))-1)

Submission status: Accepted

Solution code:
k,t=map(int,input().split())
a=list(map(int,input().split()))
for i in range(t):
    a[i]=[a[i],i]
prev=-1
if t>1:
    for i in range(k):
        a.sort(reverse=True)
        if a[0][1]==prev:
            if a[1][0]==0:
                break
            else:
                a[1][0]-=1
                prev=a[1][1]
        else:
            a[0][0]-=1
            prev=a[0][1]
    print(a[0][0])
else:
    print(a[0][0]-1)

Submission status: Accepted

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

    a = max(A)

    limit = (k+1) //2

    if k % 2 == 0:
        ans = max(0,1 + 2*(a - limit -1))
    else:
        ans = max(0,2*(a-limit))

    print(ans)

main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
#mod = 10 ** 9 + 7 
mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

K, T = MAP()
a = LIST()
ma = max(a)
left = K-ma
print(max(0, ma-left-1))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
#mod = 10 ** 9 + 7 
mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

K, T = MAP()
a = LIST()
ma = max(a)
left = sum(a)-ma
print(max(0, ma-left-1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
#mod = 10 ** 9 + 7 
mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

K, T = MAP()
a = LIST()
A_max = max(a)

if 2*A_max <= K-1:
	print(0)
else:
	c = K - A_max + 1
	print(A_max - c)

Submission status: Accepted

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

A.sort()
if sum(A[:t-1]) >= A[-1]:
    print(0)
else:
    print(A[-1]-sum(A[:t-1])-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
a = sorted(list(map(int, input().split())))
print(2 * a[-1] - k - 1 if a[-1] > k // 2 else 0)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

lst=[]
for i in range(t):
    lst.append([-a[i],i])
heapq.heapify(lst)

mae=[0,-1]
while lst:
    now,id=heapq.heappop(lst)
    now+=1
    if mae[0]!=0:
        heapq.heappush(lst,mae)
    mae=[now,id]
print(-mae[0])

Submission status: Accepted

Solution code:
k,t = map(int,input().split())
ans = 0
l = list(map(int,input().split()))
m = max(l)
if m > k//2:
    if k%2:
        print(max(0,m-(k-m)-1))
    else:
        print(m-(k-m)-1)
else:
    print(0)

Submission status: Accepted

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    k, t = mi()
    cake = lmi()
    if t == 0:
        print(cake[0] - 1)
    else:
        M = max(cake)
        others = sum(cake) - M
        if M - 1 <= others:
            print(0)
        else:
            print(M - 1 - others)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
k,t=map(int,input().split())
a=list(map(int,input().split()))
if t==1: print(a[0]-1)
else:
    temp=max(a)
    rest=sum(a)-temp
    if rest>=temp-1: print(0)
    else: print(temp-rest-1)

Submission status: Accepted

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

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

Submission status: Accepted

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

############ ---- Input Functions ---- ############
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))
    
k, t = invr()
ips = sorted(list(invr()))
rest_sum = sum(ips[:-1])
if rest_sum > ips[-1]:
    print(0)
else :
    print(ips[-1]-rest_sum-1)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
k, t = map(int, input().split())
a = list(map(int, input().split()))
ans = max(0, - sum(a) + 2 * max(a) - 1)
print(ans)

Submission status: Accepted

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

As.sort()
a = As[-1]
b = sum(As[:-1])

print(max(0,a-b-1))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

m = max(arr)
ans = m*2 - k - 1

print(max(0, ans))

Submission status: Accepted

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

m = max(a)
o = sum(a)-m

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

Submission status: Accepted

Solution code:
import heapq

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

q = []
heapq.heapify(q)

for i in range(t):
    heapq.heappush(q, [a[i] * -1, i])

ans = 0
prev = -1

while len(q) > 0:
    num, idx = heapq.heappop(q)
    if idx == prev and len(q) > 0:
        num2, idx2 = heapq.heappop(q)
        heapq.heappush(q, [num, idx])
        num, idx = num2, idx2

    if idx == prev:
        ans += 1
    num *= -1
    num -= 1
    if num > 0:
        heapq.heappush(q, [num * -1, idx])
    prev = idx

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Jun 19 16:25:46 2020

@author: NEC-PCuser
"""


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

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

a.sort()

sum_cake = 0
for i in range(len(a) - 1):
   sum_cake += a[i]

if a[len(a) - 1] <= sum_cake + 1:
   print(0)
else:
    print(a[len(a) - 1]  - sum_cake - 1)

Submission status: Accepted

Solution code:
k,t = map(int,input().split())
a = list(map(int,input().split()))
maxa = max(a)
if t == 1:
  print(k-1)
  exit()
if k//2 >= maxa:
  print(0)
else:
  print(maxa-(k-maxa)-1)

Submission status: Accepted

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

A = sorted(A)

Amax = A[-1]

Atwo = sum(A)-Amax

if T == 1:
	print(K-1)
	exit()
if T ==2:
	print(max(A[-1]-1-Atwo, 0))
	exit()

if Amax-1 > Atwo:
	print(Amax-1-Atwo)
else:
	print(0)

Submission status: Accepted

Solution code:
import sys
import heapq
K, T = map(int, input().split())
m = [-int(i) for i in input().split()]
heapq.heapify(m)

if T == 1:
    print(K-1)
    sys.exit()

while len(m) > 1:
    l = heapq.heappop(m)
    r = heapq.heappop(m)
    if r+1 != 0:
        heapq.heappush(m, l+1)
        heapq.heappush(m, r+1)
    else:
        if l+1 != 0:
            heapq.heappush(m, l+1)
if len(m) == 0:
    print(0)
else:
    print(-m[0]-1)