Problem p03148 (python)

Fixed submission:
Num,K=map(int,input().split())
L=[[]for i in range(Num+1)]
for i in range(Num):
    t,d=map(int,input().split())
    L[t].append(d)
for i in range(1,Num+1):
    L[i].sort(reverse=True)

M=[]
m=[]
for i in range(1,Num+1):
    if len(L[i])>=1:
        M.append(L[i][0])
        if len(L[i])>=2:
            for j in range(1,len(L[i])):
                m.append(L[i][j])
M.sort(reverse=True)
m.sort(reverse=True)
MM=[0]
for i in range(len(M)):
    MM.append(MM[-1]+M[i])
mm=[0]
for i in range(len(m)):
    mm.append(mm[-1]+m[i])
#print(MM)
#print(mm)
ANS=0

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5+10
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

for i in range(1,min(K,len(M))+1):
    ANS=max(i*i+MM[i]+mm[min(len(mm)-1,K-i)],ANS)
    #print(ANS,i)
print(ANS)

Buggy submission (verdict: Runtime Error):
Num,K=map(int,input().split())
L=[[]for i in range(Num+1)]
for i in range(Num):
    t,d=map(int,input().split())
    L[t].append(d)
for i in range(1,Num+1):
    L[i].sort(reverse=True)

M=[]
m=[]
for i in range(1,Num+1):
    if len(L[i])>=1:
        M.append(L[i][0])
        if len(L[i])>=2:
            for j in range(1,len(L[i])):
                m.append(L[i][j])
M.sort(reverse=True)
m.sort(reverse=True)
MM=[0]
for i in range(len(M)):
    MM.append(MM[-1]+M[i])
mm=[0]
for i in range(len(m)):
    mm.append(mm[-1]+m[i])
#print(MM)
#print(mm)
ANS=0

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5+10
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

for i in range(len(M)+1):
    ANS=max(i*i+MM[i]+mm[min(len(mm)-1,K-i)],ANS)
    #print(ANS,i)
print(ANS)

Buggy submission (verdict: Runtime Error):
N,K=map(int,input().split())

S=[[]for i in range(10**5+1)]
for i in range(N):
    a,b=map(int,input().split())
    S[a].append(b)
S.sort(reverse=True)
#print(S[:10])

k=0
o=0
E=[]
for i in range(len(S)):
    if S[i]==[]:
        break
    else:
        S[i].sort(reverse=True)
        k+=1
        o+=S[i][0]
        E.append(S[i][0])
        del S[i][0]
E.sort()
#print(S)
S.sort(reverse=True)
A=[]
if k>K:
    for i in range(k-K):
        A.append(E[i])
        o-=E[i]
    for i in range(k-K):
        del E[i]
        k-=1
#print(A)
for i in range(len(S)):
    if S[i]==[]:
        break
    else:
        for j in range(len(S[i])):
            A.append(S[i][j])
A.sort(reverse=True)
#print(A)
if K-k>0:
    for i in range(K-k):
        o+=A[i]
        del A[i]
        #print(i)
    
    #print(A)
    #print(E)
for i in range(min(K,len(A))):
    if k*k+o<=(k-1)**2+o-E[i]+A[i]:
        k=(k-1)
        o=o-E[i]+A[i]
    else:
        break
print(k*k+o)

Buggy submission (verdict: Runtime Error):
N,K=map(int,input().split())

S=[[]for i in range(10**5+1)]
for i in range(N):
    a,b=map(int,input().split())
    S[a].append(b)
S.sort(reverse=True)
#print(S[:10])

k=0
o=0
E=[]
for i in range(len(S)):
    if S[i]==[]:
        break
    else:
        S[i].sort(reverse=True)
        k+=1
        o+=S[i][0]
        E.append(S[i][0])
        del S[i][0]
E.sort()
#print(S)
S.sort(reverse=True)
A=[]
if k>K:
    for i in range(k-K):
        A.append(E[i])
        o-=E[i]
    for i in range(k-K):
        del E[i]
        k-=1
#print(A)
for i in range(len(S)):
    if S[i]==[]:
        break
    else:
        for j in range(len(S[i])):
            A.append(S[i][j])
A.sort(reverse=True)
#print(A)
if K-k>0:
    for i in range(K-k):
        o+=A[i]
        #print(i)
    del A[:i+1]
    #print(A)
    #print(E)
for i in range(min(K,len(A))):
    if k*k+o<=(k-1)**2+o-E[i]+A[i]:
        k=(k-1)
        o=o-E[i]+A[i]
    else:
        break
print(k*k+o)

Buggy submission (verdict: Runtime Error):
N,K=map(int,input().split())

S=[[]for i in range(10**5+1)]
for i in range(N):
    a,b=map(int,input().split())
    S[a].append(b)
S.sort(reverse=True)
#print(S[:10])

k=0
o=0
E=[]
for i in range(len(S)):
    if S[i]==[]:
        break
    else:
        S[i].sort(reverse=True)
        k+=1
        o+=S[i][0]
        E.append(S[i][0])
        del S[i][0]
E.sort()
#print(S)
S.sort(reverse=True)
A=[]
if k>K:
    for i in range(k-K):
        A.append(E[i])
        o-=E[i]
    for i in range(k-K):
        del E[i]
        k-=1

for i in range(len(S)):
    if S[i]==[]:
        break
    else:
        for j in range(len(S[i])):
            A.append(S[i][j])
A.sort(reverse=True)
#print(A)
if K-k>0:
    for i in range(K-k):
        o+=A[i]
        #print(i)
    del A[:i+1]
    print(A)
    print(E)
for i in range(min(K,len(A))):
    if k*k+o<(k-1)**2+o-E[i]+A[i]:
        k=(k-1)
        o=o-E[i]+A[i]
    else:
        break
print(k*k+o)

Buggy submission (verdict: Runtime Error):
N,K=map(int,input().split())

S=[[]for i in range(10**5+1)]
for i in range(N):
    a,b=map(int,input().split())
    S[a].append(b)
S.sort(reverse=True)
#print(S)

k=0
o=0
E=[]
for i in range(len(S)):
    if S[i]==[]:
        break
    else:
        k+=1
        o+=S[i][0]
        E.append(S[i][0])
        del S[i][0]
E.sort()
#print(S)
S.sort(reverse=True)
A=[]
if k>K:
    for i in range(k-K):
        A.append(E[i])
        o-=E[i]
    for i in range(k-K):
        del E[i]
        k-=1

for i in range(len(S)):
    if S[i]==[]:
        break
    else:
        for j in range(len(S[i])):
            A.append(S[i][j])
A.sort(reverse=True)
#print(A)
if K-k>0:
    for i in range(K-k):
        o+=A[i]
        #print(i)
    del A[:i+1]
    print(A)
    print(E)
for i in range(min(K,len(A))):
    if k*k+o<(k-1)**2+o-E[i]+A[i]:
        k=(k-1)
        o=o-E[i]+A[i]
    else:
        break
print(k*k+o)

Buggy submission (verdict: Runtime Error):
N,K=map(int,input().split())

S=[[]for i in range(10**1+1)]
for i in range(N):
    a,b=map(int,input().split())
    S[a].append(b)
S.sort(reverse=True)
#print(S)

k=0
o=0
E=[]
for i in range(len(S)):
    if S[i]==[]:
        break
    else:
        k+=1
        o+=S[i][0]
        E.append(S[i][0])
        del S[i][0]
E.sort()
#print(S)
S.sort(reverse=True)
A=[]
if k>K:
    for i in range(k-K):
        A.append(E[i])
        o-=E[i]
    for i in range(k-K):
        del E[i]
        k-=1

for i in range(len(S)):
    if S[i]==[]:
        break
    else:
        for j in range(len(S[i])):
            A.append(S[i][j])
A.sort(reverse=True)
#print(A)
if K-k>0:
    for i in range(K-k):
        o+=A[i]
        #print(i)
    del A[:i+1]
    print(A)
    print(E)
for i in range(min(K,len(A))):
    if k*k+o<(k-1)**2+o-E[i]+A[i]:
        k=(k-1)
        o=o-E[i]+A[i]
    else:
        break
print(k*k+o)

Buggy submission (verdict: Runtime Error):
N,K=map(int,input().split())

S=[[]for i in range(10**1+1)]
for i in range(N):
    a,b=map(int,input().split())
    S[a].append(b)
S.sort(reverse=True)
#print(S)

k=0
o=0
E=[]
for i in range(len(S)):
    if S[i]==[]:
        break
    else:
        k+=1
        o+=S[i][0]
        E.append(S[i][0])
        del S[i][0]
E.sort()
#print(S)
S.sort(reverse=True)
A=[]
if k>K:
    for i in range(k-K):
        A.append(E[i])
    for i in range(k-K):
        del E[i]
        k-=1

for i in range(len(S)):
    if S[i]==[]:
        break
    else:
        for j in range(len(S[i])):
            A.append(S[i][j])
A.sort(reverse=True)
#print(A)
if K-k>0:
    for i in range(K-k):
        o+=A[i]
        #print(i)
    del A[:i+1]
    print(A)
    print(E)
for i in range(min(K,len(A))):
    if k*k+o<(k-1)**2+o-E[i]+A[i]:
        k=(k-1)
        o=o-E[i]+A[i]
    else:
        break
print(k*k+o)

Buggy submission (verdict: Runtime Error):
N,K=map(int,input().split())

S=[[]for i in range(10**1+1)]
for i in range(N):
    a,b=map(int,input().split())
    S[a].append(b)
S.sort(reverse=True)
#print(S)

k=0
o=0
E=[]
for i in range(len(S)):
    if S[i]==[]:
        break
    else:
        k+=1
        o+=S[i][0]
        E.append(S[i][0])
        del S[i][0]
E.sort()
#print(S)
S.sort(reverse=True)
A=[]
for i in range(len(S)):
    if S[i]==[]:
        break
    else:
        for j in range(len(S[i])):
            A.append(S[i][j])
A.sort(reverse=True)
#print(A)
if K-k>0:
    for i in range(K-k):
        o+=A[i]
        #print(i)
    del A[:i+1]
    print(A)
    print(E)
for i in range(min(K,len(A))):
    if k*k+o<(k-1)**2+o-E[i]+A[i]:
        k=(k-1)
        o=o-E[i]+A[i]
    else:
        break
print(k*k+o)