Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02620 (python)

Fixed submission:
D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for i in range(D)]
t = [int(input()) for i in range(D)]
last = [[-1] for i in range(26)]
# before query
ans = 0
for i in range(D):
    op = t[i]-1
    ans += s[i][op]
    last[op].append(i)
    for j in range(26):
        ans -= c[j]*(i-last[j][-1])
    # print(ans)
from bisect import *
import random
m = int(input())
def suminc(a,b):
    return b*(b-1)//2-a*(a-1)//2
while m:
    m-=1
    update = 0
    d,q = map(int, input().split())
    # d = random.randint(1,365)
    # q = random.randint(1,26)
    d-=1
    q-=1
    oq = t[d]-1
    update += s[d][q]-s[d][oq]
    idx = bisect_left(last[oq],d)
    if idx == len(last[oq])-1:
        cnt = D - last[oq][idx]
    else:
        cnt = last[oq][idx+1] - last[oq][idx]
    update += c[oq]*suminc(0,cnt)
    cntprv = last[oq][idx] - last[oq][idx-1]
    update -= c[oq]*suminc(cntprv,cntprv+cnt)

    idx2 = bisect_left(last[q],d)-1
    if idx2 == len(last[q])-1:
        cnt = D - d
    else:
        cnt = last[q][idx2+1] - d
    if idx2 == len(last[q])-1:
        cntprv = D - last[q][idx2] - cnt
    else:
        cntprv = last[q][idx2+1] - last[q][idx2] - cnt
    update += c[q]*suminc(cntprv,cntprv+cnt)
    update -= c[q]*suminc(0,cnt)

    ans += update
    del last[oq][idx]
    last[q].insert(idx2+1,d)
    print(ans)
    t[d] = q+1

Buggy submission (verdict: Runtime Error):
D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for i in range(D)]
t = [int(input()) for i in range(D)]
last = [[-1] for i in range(26)]
# before query
ans = 0
for i in range(D):
    op = t[i]-1
    ans += s[i][op]
    last[op].append(i)
    for j in range(26):
        ans -= c[j]*(i-last[j][-1])
    # print(ans)
from bisect import *

m = int(input())
def suminc(a,b):
    return b*(b-1)//2-a*(a-1)//2
while m:
    m-=1
    update = 0
    d,q = map(int, input().split())
    d-=1
    q-=1
    oq = t[d]-1
    update += s[d][q]-s[d][oq]
    idx = bisect_left(last[oq],d)
    if idx == len(last[oq])-1:
        cnt = D - last[oq][idx]
    else:
        cnt = last[oq][idx+1] - last[oq][idx]
    update += c[oq]*suminc(0,cnt)
    cntprv = last[oq][idx] - last[oq][idx-1]
    update -= c[oq]*suminc(cntprv,cntprv+cnt)

    idx2 = bisect_left(last[q],d)-1
    if idx2 == len(last[q])-1:
        cnt = D - d
    else:
        cnt = last[oq][idx2+1] - d
    if idx2 == len(last[q])-1:
        cntprv = D - last[oq][idx2] - cnt
    else:
        cntprv = last[oq][idx2+1] - last[oq][idx2] - cnt
    update += c[q]*suminc(cntprv,cntprv+cnt)
    update -= c[q]*suminc(0,cnt)

    ans += update
    del last[oq][idx]
    last[q].insert(idx2+1,d)
    print(ans)
    t[d] = q+1
Problem p02642 (python)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))

ok = [True]*1000005

a.sort()
ans=0
for i in range(n):
    if i<n-1 and a[i]!=a[i+1] and ok[a[i]]:
        ans+=1
    elif i==n-1 and ok[a[i]]:
        ans+=1
    if ok[a[i]]:
        for j in range(a[i],1000004,a[i]):
            ok[j]=False

print(ans)

Buggy submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))

ok = [True]*100005

a.sort()
ans=0
for i in range(n):
    if i<n-1 and a[i]!=a[i+1] and ok[a[i]]:
        ans+=1
    elif i==n-1 and ok[a[i]]:
        ans+=1
    if ok[a[i]]:
        for j in range(a[i],100004,a[i]):
            ok[j]=False

print(ans)
Problem p02657 (python)

Fixed submission:
a,b = map(int, input().split())

print(a*b)

Buggy submission (verdict: Runtime Error):
a,b = int(input())

print(a*b)
Problem p02692 (python)

Fixed submission:
n,a,b,c = map(int, input().split())
op = [input() for i in range(n)]

val=[a,b,c]
flag=True
ansls=list()

for i in range(n):
    s1=ord(op[i][0])-ord('A')
    s2=ord(op[i][1])-ord('A')
    if val[s1]>val[s2]:
        ansls.append(s2)
        val[s2]+=1
        val[s1]-=1
    elif val[s1]<val[s2] or i+1==n:
        ansls.append(s1)
        val[s1]+=1
        val[s2]-=1
    else:
        s1n = ord(op[i+1][0])-ord('A')
        s2n = ord(op[i+1][1])-ord('A')
        nxt = set([s1,s2]) & set([s1n,s2n])
        nxt = list(nxt)[0]
        ansls.append(nxt)
        val[nxt]+=1
        if nxt==s1:
            val[s2]-=1
        else:
            val[s1]-=1
    if min(val)<0:
        flag=False
        break

if flag:
    print('Yes')
    for i in range(n):
        print(chr(ansls[i]+ord('A')))
else:
    print('No')

Buggy submission (verdict: Runtime Error):
n,a,b,c = map(int, input().split())
op = [input() for i in range(n)]

val=[a,b,c]
flag=True
ansls=list()

for i in range(n):
    s1=ord(op[i][0])-ord('A')
    s2=ord(op[i][1])-ord('A')
    if val[s1]>val[s2]:
        ansls.append(s2)
        val[s2]+=1
        val[s1]-=1
    elif val[s1]<val[s2]:
        ansls.append(s1)
        val[s1]+=1
        val[s2]-=1
    else:
        s1n = ord(op[i+1][0])-ord('A')
        s2n = ord(op[i+1][1])-ord('A')
        nxt = set([s1,s2]) & set([s1n,s2n])
        nxt = list(nxt)[0]
        ansls.append(nxt)
        val[nxt]+=1
        if nxt==s1:
            val[s2]-=1
        else:
            val[s1]-=1
    if min(val)<0:
        flag=False
        break

if flag:
    print('Yes')
    for i in range(n):
        print(chr(ansls[i]+ord('A')))
else:
    print('No')
Problem p02798 (python)

Fixed submission:
from itertools import combinations
import sys
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a2=list()
b2=list()

if n==1:
    print(0)
    sys.exit()
    
for i in range(n):
    if i%2:
        b2.append(a[i])
        a2.append(b[i])
    else:
        a2.append(a[i])
        b2.append(b[i])

ans=10**9
for idx in combinations(range(0,n), (n+1)//2):
    a3=list()
    b3=list()
    flag=True
    for i in range(n):
        if i in idx:
            a3.append([a2[i], i])
        else:
            b3.append([b2[i], i])
    a3.sort(key=lambda x:x[0])
    b3.sort(key=lambda x:x[0])

    for i in range(len(b3)-1):
        if a3[i][0]>b3[i][0] or a3[i+1][0]<b3[i][0]:
            flag=False
    if len(a3)>len(b3):
        if a3[-1][0]<b3[-1][0] or a3[-2][0]>b3[-1][0]:
            flag=False
    elif a3[-1][0]>b3[-1][0]:
        flag=False

    if flag:
        ansidx = list()
        for i in range(len(b3)):
            ansidx.append(a3[i][1])
            ansidx.append(b3[i][1])
        if len(a3)>len(b3):
            ansidx.append(a3[-1][1])

        swap=0
        for i in range(n):
            for j in range(i,n):
                if ansidx[i]>ansidx[j]:
                    swap+=1
        ans= min(ans, swap)

if ans==10**9:
    print('-1')
else:
    print(ans)

Buggy submission (verdict: Runtime Error):
from itertools import combinations

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a2=list()
b2=list()

for i in range(n):
    if i%2:
        b2.append(a[i])
        a2.append(b[i])
    else:
        a2.append(a[i])
        b2.append(b[i])

ans=10**9
for idx in combinations(range(0,n), (n+1)//2):
    a3=list()
    b3=list()
    flag=True
    for i in range(n):
        if i in idx:
            a3.append([a2[i], i])
        else:
            b3.append([b2[i], i])
    a3.sort(key=lambda x:x[0])
    b3.sort(key=lambda x:x[0])

    for i in range(len(b3)-1):
        if a3[i][0]>b3[i][0] or a3[i+1][0]<b3[i][0]:
            flag=False
    if len(a3)>len(b3):
        if a3[-1][0]<b3[-1][0] or a3[-2][0]>b3[-1][0]:
            flag=False
    elif a3[-1][0]>b3[-1][0]:
        flag=False

    if flag:
        ansidx = list()
        for i in range(len(b3)):
            ansidx.append(a3[i][1])
            ansidx.append(b3[i][1])
        if len(a3)>len(b3):
            ansidx.append(a3[-1][1])

        swap=0
        for i in range(n):
            for j in range(i,n):
                if ansidx[i]>ansidx[j]:
                    swap+=1
        ans= min(ans, swap)

if ans==10**9:
    print('-1')
else:
    print(ans)
Problem p02839 (python)

Fixed submission:
h, w = map(int, input().split())
lsa = [list(map(int, input().split())) for i in range(h)]
lsb = [list(map(int, input().split())) for i in range(h)]
ls = [[abs(lsa[i][j] - lsb[i][j]) for j in range(w)] for i in range(h)]
bias = 80*80*80

dp = [[0 for _ in range(w)] for _ in range(h)]

dp[0][0] = 1 << ls[0][0]+bias

for i in range(h):
    for j in range(w):

        if j != 0:  
            dp[i][j] |= dp[i][j-1] << ls[i][j]
            dp[i][j] |= dp[i][j-1] >> ls[i][j]

        if i != 0:
            dp[i][j] |= dp[i-1][j] << ls[i][j]
            dp[i][j] |= dp[i-1][j] >> ls[i][j]

ans = dp[h-1][w-1] >> bias
idx = 0
while(1):
    if 1 << idx & ans:
        break
    idx += 1
print(idx)

Buggy submission (verdict: Runtime Error):
h, w = map(int, input().split())
lsa = [list(map(int, input().split())) for i in range(h)]
lsb = [list(map(int, input().split())) for i in range(h)]
ls = [[abs(lsa[i][j] - lsb[i][j]) for j in range(w)] for i in range(h)]

p=0
for i in range(h):
    p+= sum(ls[i])

dp = [[[False]*p for _ in range(w)] for _ in range(h)]

dp[0][0][ls[0][0]] = True

for i in range(h):
    for j in range(w):

        if j != 0:  
            for k in range(p):
                if dp[i][j-1][k]:
                    dp[i][j][k+ls[i][j]] = True
                    dp[i][j][abs(k-ls[i][j])] = True

        if i != 0:
            for k in range(p):
                if dp[i-1][j][k]:
                    dp[i][j][k+ls[i][j]] = True
                    dp[i][j][abs(k-ls[i][j])] = True

for i in range(p):
    if dp[h-1][w-1][i]:
        break

print(i)
Problem p02855 (python)

Fixed submission:
h,w,k = map(int, input().split())
ls = [list(input()) for i in range(h)]
ansls = [[0]*w for _ in range(h)]
absent = []
idx = 1
for i in range(h):
    if ls[i] == ['.']*w:
        absent.append(i)
    else:
        count=0
        for j in range(w):
            if ls[i][j] == "#":
                if count>0:
                    idx+=1
                count+=1
            ansls[i][j] = idx
        idx+=1

for i in absent:
    idx = i
    while idx in absent:
        idx+=1
    if idx>=h:
        idx = i
        while idx in absent:
            idx-=1
    ansls[i] = ansls[idx]

for l in ansls:
    print(*l)

Buggy submission (verdict: Runtime Error):
h,w,k = map(int, input().split())
ls = [list(input()) for i in range(h)]
ansls = [[0]*w for _ in range(h)]
absent = []
idx = 1
for i in range(h):
    if ls[i] == ['.']*w:
        absent.append(i)
    else:
        count=0
        for j in range(w):
            if ls[i][j] == "#":
                if count>0:
                    idx+=1
                count+=1
            ansls[i][j] = idx
        idx+=1

for i in absent:
    idx = i
    if i<h-1:
        while idx in absent:
            idx+=1
    else:
        while idx in absent:
            idx-=1
    ansls[i] = ansls[idx]

for l in ansls:
    print(*l)

Buggy submission (verdict: Runtime Error):
import bisect
h, w, k = map(int, input().split())
ls = [list(input()) for _ in range(h)]

idxls = [0]*k
a = 0
rawls = set([-1, h])
for i in range(h):
    for j in range(w):
        if ls[i][j] == '#':
            idxls[a] = [i, j]
            rawls.add(i)
            a += 1

ansls = [[0 for _ in range(w)] for _ in range(h)]

rawls = list(rawls)
rawls.sort()
diffls= [0]*(len(rawls)-1)
for i in range(len(rawls)-1):
    diffls[i] = rawls[i+1] - rawls[i]

#paint raw
a = 0
for i in rawls[1:-1]:
    for j in range(w):
        if ls[i][j] == '#':
            a += 1
        for k in range(diffls[i+1]):
            ansls[i+k][j] = max(a,1)

a = 0
i = rawls[1]
for j in range(w):
    if ls[i][j] == '#':
        a += 1
    for k in range(diffls[0]):
        ansls[i-k][j] = max(a,1)

for l in ansls:
    print(*l)
Problem p02867 (python)

Fixed submission:
n = int(input())
lsa = list(map(int, input().split()))
lsb = list(map(int, input().split()))

ls = [[a, b] for a, b in zip(lsa, lsb)]
ls.sort(key=lambda x: x[1])
lsa = [l[0] for l in ls]
lsb = [l[1] for l in ls]

lsasort = sorted(lsa)
for i in range(n):
    if lsasort[i]>lsb[i]:
        flag = False
        break
else:
    flag = True

if flag:
    lscycle = [[p, q] for p, q in zip(range(n), lsa)]
    lscycle.sort(key=lambda x: x[1])

    count=0
    idx=0
    while True:
        idx=lscycle[idx][0]
        count+=1
        if idx == 0:
            break

    if count != n:
        flag = True
    else:
        for i in range(n-1):
            if lsasort[i+1] <= lsb[i]:
                flag = True
                break
        else:
            flag = False

if flag:
    print("Yes")
else:
    print("No")

Buggy submission (verdict: Runtime Error):
import numpy as np

n = int(input())
A = np.asarray(list(map(int, input().split())))
B = np.asarray(list(map(int, input().split())))
AB = np.stack((A, B), axis=1)
AB = AB[np.argsort(AB[:, 1])]

flag = False
k = 0
while(not flag and k<n):
    if AB[k,0] <= AB[k,1]:
        ABd = np.delete(AB, k, 0)

        As = ABd[:, 0]

        As.sort()

        for i in range(n-1):
            if As[i] > ABd[i, 1]:
                break
        else:
            flag = True

    k += 1

if flag:
    print('Yes')
else:
    print('No')

Buggy submission (verdict: Runtime Error):
import numpy as np

n = int(input())
A = np.asarray(list(map(int, input().split())))
B = np.asarray(list(map(int, input().split())))
AB = np.stack((A, B), axis=1)
AB = AB[np.argsort(AB[:, 1])]

flag = False
k = 0
while(not flag and k<n):
    if AB[k,0] <= AB[k,1]:
        ABd = np.delete(AB, k, 0)

        As = ABd[:, 0]

        As.sort()

        for i in range(n-1):
            if As[i] > ABd[i, 1]:
                break
        else:
            flag = True

    k += 1

if flag:
    print('Yes')
else:
    print('No')
Problem p03111 (python)

Fixed submission:
N,A,B,C = map(int,input().split())
l = [int(input()) for i in range(N)]
INF = 10 ** 9

def ans(cur,a,b,c):
    
    if cur == N:
        return abs(a-A) + abs(b-B) + abs(c-C) - 30 if min(a,b,c) > 0 else INF
    
    ret0 = ans(cur + 1,a,b,c) 
    ret1 = ans(cur + 1,a + l[cur],b,c) + 10
    ret2 = ans(cur + 1,a,b + l[cur],c) + 10
    ret3 = ans(cur + 1,a,b,c + l[cur]) + 10

    return min(ret0,ret1,ret2,ret3)

print(ans(0,0,0,0))

Buggy submission (verdict: Runtime Error):
N,A,B,C = map(int,input().split())
l = [input() for i in range(N)]
INF = 10 ** 9

def ans(cur,a,b,c):
    
    if cur == N:
        return abs(a-A) + abs(b-B) + abs(c-C) - 30 if min(a,b,c) > 0 else INF
    
    ret0 = ans(cur + 1,a,b,c) 
    ret1 = ans(cur + 1,a + l[cur],b,c) + 10
    ret2 = ans(cur + 1,a,b + l[cur],c) + 10
    ret3 = ans(cur + 1,a,b,c + l[cur]) + 10

    return min(ret0,ret1,ret2,ret3)

print(ans(0,0,0,0))
Problem p02574 (python)

Fixed submission:
from itertools import groupby

class Osa_k:
    def __init__(self, n_max):
        self.min_factor = min_factor = list(range(n_max+1))
        for i in range(2, int(n_max**0.5)+1):
            if min_factor[i] == i:
                for j in range(i*i, n_max+1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1  # 最悪ケースでは速くなる
        res = [2] * n_twoes
        n >>= n_twoes
        while n > 1:
            p = min_factor[n]
            res.append(p)
            n //= p
        return res

def main():
    N = int(input())
    A = list(map(int, input().split()))
    osa_k = Osa_k(1010101)
    Factors = [osa_k(a) for a in A]
    factors = Factors[0]
    st0 = set(factors)  # 0 になれば setwize
    st1 = set(factors)  # 重複しなければ pairwise
    pairwise = True
    for factors in Factors[1:]:
        st = []
        for f, _ in groupby(factors):
            if f in st1:
                pairwise = False
            else:
                st1.add(f)
            st.append(f)
        st0 &= set(st)
    if pairwise:
        print("pairwise coprime")
    elif not st0:
        print("setwise coprime")
    else:
        print("not coprime")

main()

Buggy submission (verdict: Runtime Error):
from itertools import groupby

def fast_prime_factorization_many(lst):
    # 素因数分解（ロー法、複数）
    from subprocess import Popen, PIPE
    res = Popen(["factor"] + list(map(str, lst)), stdout=PIPE).communicate()[0].split(b"\n")[:-1]
    return [list(map(int, r.split()[1:])) for r in res]

def main():
    N = int(input())
    A = list(map(int, input().split()))
    Factors = fast_prime_factorization_many(A)
    factors = Factors[0]
    st0 = set(factors)  # 0 になれば setwize
    st1 = set(factors)  # 重複しなければ pairwise
    pairwise = True
    for factors in Factors[1:]:
        for f, _ in groupby(factors):
            if f in st1:
                pairwise = False
            else:
                st1.add(f)
            if f in st0:
                st0.remove(f)
    if pairwise:
        print("pairwise coprime")
    elif not st0:
        print("setwise coprime")
    else:
        print("not coprime")

main()
Problem p02825 (python)

Fixed submission:
N = int(input())
if N==2:
    print(-1)
    exit()
if N==3:
    print("""aa.
..b
..b""")
    exit()
P4 = """abcc
abdd
ccab
ddab"""
P5 = """abbaa
a..db
b..db
bcc.a
aabba"""
P6 = """aa.ccd
..bd.d
..bdcc
ccdaa.
d.d..b
dcc..b"""
P7 = """.ccbbaa
c...ccd
c...d.d
b...dcc
bccd...
ad.d...
adcc..."""
P = [P4, P5, P6, P7]
def construct(L):
    P_split = [p.split() for p in P]
    ans = []
    offset = 0
    for l in L:
        r = N-offset-l
        for p in P_split[l-4]:
            ans.append("."*offset + p + "."*r)
        offset += l
    return "\n".join(ans)
def sep(n):  # 4 と 5 に分ける
    if n==6:
        return [6]
    elif n==7:
        return [7]
    elif n==11:
        return [5, 6]
    res = [4] * (n//4)
    for i in range(n%4):
        res[i] += 1
    return res
print(construct(sep(N)))

Buggy submission (verdict: Runtime Error):
N = int(input())
if N==2:
    assert False
print(-1)
Problem p02840 (python)

Fixed submission:
def solve(N, X, D):
    if D == 0:
        if X == 0:
            return 1
        return N+1
    L = {0: [(0, 1), (1, -1)]}
    coef_l = 0
    coef_r = 1
    for coef_x in range(1, N+1):
        m = X * coef_x % D
        l = X * coef_x // D + coef_l
        r = X * coef_x // D + coef_x * N - coef_r
        coef_l = coef_r
        coef_r += coef_x + 1
        if m not in L:
            L[m] = []
        L[m].append((l, 1))
        L[m].append((r+1, -1))
    ans = 0
    #print(L)
    for Q in L.values():
        Q.sort()
        cnt = 0
        last = None
        for val, sign in Q:
            if cnt > 0:
                ans += val - last
            cnt += sign
            last = val
    return ans

N, X, D = map(int, input().split())
print(solve(N, X, D))

Buggy submission (verdict: Runtime Error):
def solve(N, X, D):
    L = {0: [(0, 1), (1, -1)]}
    coef_l = 0
    coef_r = 1
    for coef_x in range(1, N+1):
        m = X * coef_x % D
        l = X * coef_x // D + coef_l
        r = X * coef_x // D + coef_x * N - coef_r
        coef_l = coef_r
        coef_r += coef_x + 1
        if m not in L:
            L[m] = []
        L[m].append((l, 1))
        L[m].append((r+1, -1))
    ans = 0
    #print(L)
    for Q in L.values():
        Q.sort()
        cnt = 0
        last = None
        for val, sign in Q:
            if cnt > 0:
                ans += val - last
            cnt += sign
            last = val
    return ans

N, X, D = map(int, input().split())
print(solve(N, X, D))
Problem p02846 (python)

Fixed submission:
import sys
T1, T2, A1, A2, B1, B2 = map(int, sys.stdin.read().split())
a1, b1 = T1*A1, T1*B1
a2, b2 = T2*A2, T2*B2
sa, sb = a1+a2, b1+b2
if sa==sb:
    print("infinity")
    exit()
if sa < sb:
    a1, a2, b1, b2, sa, sb = b1, b2, a1, a2, sb, sa
# 2*n-1 回以上出会うか
ok = 0
ng = 10**1800
a = 0
while ok+1 < ng:
    c = (ok+ng)//2
    if (c-1)*sa+a1 <= (c-1)*sb+b1:
        if (c - 1) * sa + a1 == (c - 1) * sb + b1:
            a = -1
        ok = c
    else:
        ng = c
if ok > 10**1799:
    print("a")
    print("infinity")
else:
    print(max(ok*2-1+a, 0))

Buggy submission (verdict: Runtime Error):
import sys
T1, T2, A1, A2, B1, B2 = map(int, sys.stdin.read().split())
a1, b1 = T1*A1, T1*B1
a2, b2 = T2*A2, T2*B2
sa, sb = a1+a2, b1+b2
if sa==sb:
    print("infinity")
    exit()
if sa < sb:
    a1, a2, b1, b2, sa, ab = b1, b2, a1, a2, sb, sa

# 2*n-1 回以上出会うか
ok = 0
ng = 10**1800
a = 0
while ok+1 < ng:
    c = (ok+ng)//2
    if (c-1)*sa+a1 <= (c-1)*sb+b1:
        if (c - 1) * sa + a1 == (c - 1) * sb + b1:
            a = 1
        ok = c
    else:
        ng = c
if ok > 10**1799:
    assert False
    print("infinity")
else:
    print(max(ok*2-1+a, 0))
Problem p02926 (python)

Fixed submission:
# 凸包 Monotone Chain O(nlogn)
def det(p, q):
    return p[0]*q[1] - p[1]*q[0]
def sub(p, q):
    return (p[0]-q[0], p[1]-q[1])
def get_convex_hull(points):
    n = len(points)
    points.sort()
    size_convex_hull = 0
    ch = []
    for i in range(n):
        while size_convex_hull > 1:
            v_cur = sub(ch[-1], ch[-2])
            v_new = sub(points[i], ch[-2])
            if det(v_cur, v_new) > 0:
                break
            size_convex_hull -= 1
            ch.pop()
        ch.append(points[i])
        size_convex_hull += 1

    t = size_convex_hull
    for i in range(n-2, -1, -1):
        while size_convex_hull > t:
            v_cur = sub(ch[-1], ch[-2])
            v_new = sub(points[i], ch[-2])
            if det(v_cur, v_new) > 0:
                break
            size_convex_hull -= 1
            ch.pop()
        ch.append(points[i])
        size_convex_hull += 1

    return ch[:-1]

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
ps = [(0, 0)]
for x, y in XY:
    ps_new = ps[:]
    for x_, y_ in ps:
        ps_new.append((x+x_, y+y_))
    ps = get_convex_hull(ps_new)
ans = 0
for x, y in ps:
    ans = max(ans, x*x+y*y)
print(ans ** 0.5)

Buggy submission (verdict: Runtime Error):
# 凸包 Monotone Chain O(nlogn)
# 参考: https://matsu7874.hatenablog.com/entry/2018/12/17/025713
def get_convex_hull(points):
    from itertools import itemgetter
    def det(p, q):
        return p[0] * q[1] - p[1] * q[0]
    def sub(p, q):
        return (p[0] - q[0], p[1] - q[1])
    points.sort(key=itemgetter(0))
    ch = []
    for p in points:
        while len(ch) > 1:
            v_cur = sub(ch[-1], ch[-2])
            v_new = sub(p, ch[-2])
            if det(v_cur, v_new) > 0:
                break
            ch.pop()
        ch.append(p)
    t = len(ch)
    for p in points[-2::-1]:
        while len(ch) > t:
            v_cur = sub(ch[-1], ch[-2])
            v_new = sub(p, ch[-2])
            if det(v_cur, v_new) > 0:
                break
            ch.pop()
        ch.append(p)
    return ch[:-1]
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
ps = [(0, 0)]
for x, y in XY:
    ps_new = ps[:]
    for x_, y_ in ps:
        ps_new.append((x+x_, y+y_))
    ps = get_convex_hull(ps_new)
ans = 0
for x, y in ps:
    ans = max(ans, x*x+y*y)
print(ans ** 0.5)
Problem p02936 (python)

Fixed submission:
import sys
input = sys.stdin.readline

import sys
sys.setrecursionlimit(500000)
N, Q = map(int, input().split())
E = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
C = [0] * (N+1)
for _ in range(Q):
    p, x = map(int, input().split())
    C[p] += x
Ans = [0] * (N+1)
def dfs(v, p, a):
    a += C[v]
    Ans[v] = a
    for u in E[v]:
        if u!=p:
            dfs(u, v, a)
dfs(1, 0, 0)
print(" ".join(map(str, Ans[1:])))

Buggy submission (verdict: Runtime Error):
N, Q = map(int, input().split())
E = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
C = [0] * (N+1)
for _ in range(Q):
    p, x = map(int, input().split())
    C[p] += x

Ans = [0] * (N+1)
def dfs(v, p, a):
    global ans
    a += C[v]
    Ans[v] = a
    for u in E[v]:
        if u!=p:
            dfs(u, v, a)
dfs(1, 0, 0)
print(" ".join(map(str, Ans[1:])))