Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
R, C, K = map(int, input().split())
RC = [[0] * C for _ in range(R)]
for _ in range(K):
    r, c, v = map(int, input().split())
    RC[r-1][c-1] = v


def solve():
    memo = [[[0] * 4 for _ in range(C+1)] for _ in range(R+1)]
    for r in range(1,R+1):
        for c in range(1,C+1):
            v = RC[r-1][c-1]
            memo[r][c][0] = max(memo[r-1][c][3], memo[r][c-1][0])
            memo[r][c][1] = max(memo[r][c][0] + v, memo[r][c-1][1])
            memo[r][c][2] = max(memo[r][c][1], memo[r][c-1][1] + v, memo[r][c-1][2])
            memo[r][c][3] = max(memo[r][c][2], memo[r][c-1][2] + v, memo[r][c-1][3])
    return memo[-1][-1][3]

if __name__ == "__main__":
    print(solve())


Fixed submission:
R, C, K = map(int, input().split())
RC = [[0] * C for _ in range(R)]
for _ in range(K):
    r, c, v = map(int, input().split())
    RC[r-1][c-1] = v


def solve():
    memo = [[0] * 4 for _ in range(C+1)]
    prev = [[0] * 4 for _ in range(C+1)]
    for r in range(1,R+1):
        prev, memo = memo, prev
        for c in range(1,C+1):
            v = RC[r-1][c-1]
            memo[c][0] = max(prev[c][3], memo[c-1][0])
            memo[c][1] = max(memo[c][0] + v, memo[c-1][1])
            memo[c][2] = max(memo[c][1], memo[c-1][1] + v, memo[c-1][2])
            memo[c][3] = max(memo[c][2], memo[c-1][2] + v, memo[c-1][3])
    return memo[-1][3]

if __name__ == "__main__":
    print(solve())
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9 + 7
K = int(input())
S = len(input())

FCT = [1]
for i in range(1, K+S+1):
    FCT.append((FCT[-1] * i)%MOD)

def pmu(n, r, mod=MOD):
    return (FCT[n] * pow(FCT[n-r], mod-2, mod)) % mod

def cmb(n, r, mod=MOD):
    return (pmu(n, r) * pow(FCT[r], mod-2, mod)) % mod

def solve():
    ans = 1
    for i in range(S+1, K+S+1):
        ans = (ans*26) % MOD
        add = pow(25, i-S, MOD)
        add = (add * cmb(i-1, i-S)) % MOD
        ans = (ans + add) % MOD
    return ans

if __name__ == "__main__":
    print(solve())


Fixed submission:
MOD = 10**9 + 7
K = int(input())
S = len(input())

FCT = [1]
for i in range(1, K+S+1):
    FCT.append((FCT[-1] * i)%MOD)

def pmu(n, r, mod=MOD):
    return (FCT[n] * pow(FCT[n-r], mod-2, mod)) % mod

def cmb(n, r, mod=MOD):
    return (pmu(n, r) * pow(FCT[r], mod-2, mod)) % mod

def solve():
    ans = 1
    for i in range(S+1, K+S+1):
        ans = (ans*26) % MOD
        add = pow(25, i-S, MOD)
        add = (add * cmb(i-1, i-S)) % MOD
        ans = (ans + add) % MOD
    return ans

if __name__ == "__main__":
    print(solve())
Buggy python submission (verdict: Runtime Error):
M = 10**6
N = int(input())
A = list(map(int, input().split()))


def solve():
    memo = [0] * M
    for a in A:
        i = 1
        while i*a < M:
            memo[i*a] += 1
            i += 1

    count = 0
    for a in A:
        if memo[a] == 1:
            count += 1

    return count

if __name__ == "__main__":
    print(solve())


Fixed submission:
M = 10**6
N = int(input())
A = list(map(int, input().split()))


def solve():
    amax = max(A)+1
    memo = [0] * amax
    for a in A:
        i = 1
        while i*a < amax:
            memo[i*a] += 1
            i += 1

    count = 0
    for a in A:
        if memo[a] == 1:
            count += 1

    return count

if __name__ == "__main__":
    print(solve())
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
N = int(input())
MAXBIT = 60
MOD = 10 ** 9 + 7
A = list(map(int, input().split()))
B = []
C = [[] for _ in range(MAXBIT)]
for a in A:
    for d in range(MAXBIT):
        C[d].append(a >> d & 1)
ans = 0
for d in range(MAXBIT):
    num0 = C[d].count(0)
    num1 = N - num0
    ans += (num0 * num1) * (2 ** d)
    ans %= MOD
print(ans)

Fixed submission:
from collections import Counter
N = int(input())
MAXBIT = 60
MOD = 10 ** 9 + 7
A = list(map(int, input().split()))
B = []
C = [[] for _ in range(MAXBIT)]
for a in A:
    for d in range(MAXBIT):
        C[d].append(a >> d & 1)
ans = 0
for d in range(MAXBIT):
    num0 = C[d].count(0)
    num1 = N - num0
    ans += ((num0 * num1) % MOD) * pow(2, d, MOD)
    ans %= MOD
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
N = int(input())
MAXBIT = 60
MOD = 10 ** 9 + 7
A = list(map(int, input().split()))
B = []
C = [[] for _ in range(MAXBIT)]
for a in A:
    b = format(a, '0'+str(MAXBIT)+'b')
    for d in range(MAXBIT):
        # C[d].update([b[d]])
        C[d].append(int(b[d]))
ans = 0
for d in range(MAXBIT):
    num0 = C[d].count(0)
    num1 = N - num0
    ans += (num0 * num1) * (2 ** (MAXBIT-d-1))
    ans %= MOD
print(ans)

Fixed submission:
from collections import Counter
N = int(input())
MAXBIT = 60
MOD = 10 ** 9 + 7
A = list(map(int, input().split()))
B = []
C = [[] for _ in range(MAXBIT)]
for a in A:
    for d in range(MAXBIT):
        C[d].append(a >> d & 1)
ans = 0
for d in range(MAXBIT):
    num0 = C[d].count(0)
    num1 = N - num0
    ans += ((num0 * num1) % MOD) * pow(2, d, MOD)
    ans %= MOD
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
N = int(input())
MAXBIT = 60
MOD = 10 ** 9 + 7
A = list(map(int, input().split()))
B = []
C = [Counter() for _ in range(MAXBIT)]
for a in A:
    b = format(a, '0'+str(MAXBIT)+'b')
    for d in range(MAXBIT):
        C[d].update([b[d]])
ans = 0
for d in range(MAXBIT):
    ans += (C[d]['0'] * C[d]['1']) * (2 ** (MAXBIT-d-1))
    ans %= MOD
print(ans)

Fixed submission:
from collections import Counter
N = int(input())
MAXBIT = 60
MOD = 10 ** 9 + 7
A = list(map(int, input().split()))
B = []
C = [[] for _ in range(MAXBIT)]
for a in A:
    for d in range(MAXBIT):
        C[d].append(a >> d & 1)
ans = 0
for d in range(MAXBIT):
    num0 = C[d].count(0)
    num1 = N - num0
    ans += ((num0 * num1) % MOD) * pow(2, d, MOD)
    ans %= MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from re import match
N = int(input())
S = input()

cnt = 0
for i in range(1000):
    s = '{:03}'.format(i)
    if match('.*' + s[0] + '.*' + s[1] +'.*' + s[2], S):
        cnt += 1

print(cnt)


Fixed submission:
N = int(input())
S = input()

def search(c, text):
    pos = -1
    for i, s in enumerate(text):
        if s == c:
            pos = i
            break
    return pos

cnt = 0
for i in range(10):
    ip = search(str(i), S[0:])
    if ip < 0:
        continue
    for j in range(10):
        jp = search(str(j), S[ip+1:])
        if jp < 0:
            continue
        for k in range(10):
            kp = search(str(k), S[ip+jp+2:])
            if kp < 0:
                continue
            cnt += 1

print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)

lo, hi = 0, max(a*f for (a, f) in zip(A,F))
while lo < hi:
    mid = (lo + hi)//2
    rsd = K
    possible = True
    for a, f in zip(A,F):
        rsd -= ceil(max(a*f-mid, 0)/f)
        if rsd < 0:
            possible = False
            break
    if possible:
        hi = mid
    else:
        lo = mid+1

print(lo)


Fixed submission:
from math import ceil
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)

lo, hi = 0, max(a*f for (a, f) in zip(A,F))
while lo < hi:
    mid = (lo + hi)//2
    rsd = K
    possible = True
    for a, f in zip(A,F):
        rsd -= ceil(max(a*f-mid, 0)/f)
        if rsd < 0:
            possible = False
            break
    if possible:
        hi = mid
    else:
        lo = mid+1

print(lo)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
X = input()
MOD = 998244353

ans = 0
memo = dict()

# def get_divisor(n):
#     '''nの約数を返す
#     '''
#     d = set()
#     for i in range(1, int(n**0.5)+1):
#         if n % i == 0:
#             d.add(i)
#             d.add(n//i)
#     return d

def get_oddivisor(n):
    '''nの約数のうち商が奇数のものを返す
    '''
    d = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i%2 == 1:
                d.add(n//i)
            if (n//i)%2 == 1:
                d.add(i)
    return d

D = list(get_oddivisor(N))
D.sort()

def alternate(x, n):
    '''x: 00101, y: 11010, z: (00101)(11010)... n times
    '''
    y = ('0'*len(x) + bin(int(x,2) ^ (2**len(x)-1))[2:])[-len(x):]
    z = (x + y) * (n//2)
    if n%2 == 1:
        z += x
    return z

for d in D:
    cnt = int(X[:d], 2)
    if int(X, 2) >= int(alternate(X[:d], N//d), 2):
        cnt += 1
    dd = list(get_oddivisor(d))
    for ddd in dd:
        if ddd != d:
            cnt -= memo[ddd]
    memo[d] = cnt
    ans += cnt * 2 * d
    ans %= 998244353

print(ans)


Fixed submission:
N = int(input())
X = input()
MOD = 998244353

ans = 0
memo = dict()

# def get_divisor(n):
#     '''nの約数を返す
#     '''
#     d = set()
#     for i in range(1, int(n**0.5)+1):
#         if n % i == 0:
#             d.add(i)
#             d.add(n//i)
#     return d

def get_oddivisor(n):
    '''nの約数のうち商が奇数のものを返す
    '''
    d = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i%2 == 1:
                d.add(n//i)
            if (n//i)%2 == 1:
                d.add(i)
    return d

D = list(get_oddivisor(N))
D.sort()

def alternate(x, n):
    '''x: 00101, y: 11010, z: (00101)(11010)... n times
    '''
    y = ('0'*len(x) + bin(int(x,2) ^ (2**len(x)-1))[2:])[-len(x):]
    z = (x + y) * (n//2)
    if n%2 == 1:
        z += x
    return z

for d in D:
    cnt = int(X[:d], 2)
    if int(X, 2) >= int(alternate(X[:d], N//d), 2):
        cnt += 1
    dd = list(get_oddivisor(d))
    for ddd in dd:
        if ddd != d:
            cnt -= memo[ddd]
    memo[d] = cnt
    ans += cnt * 2 * d
    ans %= 998244353

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from math import cos, sin, pi
from itertools import combinations
N, L = map(int, input().split())
T = [int(input()) for _ in range(N)]
PI2oL = 2*pi/L

csum, ssum = 0, 0
count = 0
for i, j in combinations(range(N), 2):
    count += 1
    mid1, num2 = (T[i] + T[j]) / 2, j - i - 1
    mid2, num1 = (mid1 + L/2) % L, N - num2 - 2
    csum += cos(PI2oL*mid1) * num1 + cos(PI2oL*mid2) * num2
    ssum += sin(PI2oL*mid1) * num1 + sin(PI2oL*mid2) * num2

print(csum/count/(N-2)*3, ssum/count/(N-2)*3)


Fixed submission:
from math import cos, sin, pi
from itertools import combinations
N, L = map(int, input().split())
T = [int(input()) for _ in range(N)]
PI2oL = 2*pi/L

csum, ssum = 0, 0
count = 0
for i, j in combinations(range(N), 2):
    count += 1
    mid1, num2 = (T[i] + T[j]) / 2, j - i - 1
    mid2, num1 = (mid1 + L/2) % L, N - num2 - 2
    csum += cos(PI2oL*mid1) * num1 + cos(PI2oL*mid2) * num2
    ssum += sin(PI2oL*mid1) * num1 + sin(PI2oL*mid2) * num2

print(csum/count/(N-2)*3, ssum/count/(N-2)*3)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

dp = [[0] * N for _ in range(N)]

dp[-1] = [1 if s == S[-1] else 0 for s in S]
for i in range(N-2, -1, -1):
    dp[i][-1] = 1 if S[i] == S[-1] else 0
    for j in range(N-2, -1, -1):
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1

ans = 0
for i in range(N):
    for j in range(i+1, N):
        if dp[i][j] > 0:
            ans = max(ans, min(dp[i][j], j-i))

print(ans)


Fixed submission:
N = int(input())
S = input()

dp = [[0] * N for _ in range(N)]

dp[-1] = [1 if s == S[-1] else 0 for s in S]
for i in range(N-2, -1, -1):
    dp[i][-1] = 1 if S[i] == S[-1] else 0
    for j in range(N-2, -1, -1):
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1

ans = 0
for i in range(N):
    for j in range(i+1, N):
        if dp[i][j] > 0:
            ans = max(ans, min(dp[i][j], j-i))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import insort, bisect
N = int(input())
P = list(map(int, input().split()))

I = [0] * N
for i in range(N):
    I[P[i]-1] = i

ans = 0
memo = [I[N-1]]

for p in range(N-1, 0, -1):
    i = I[p-1]
    b = bisect(memo, i)
    l1 = memo[b-1] if b > 0 else -1
    l2 = memo[b-2] if b > 1 else -1
    r1 = memo[b+0] if b < N-p else N
    r2 = memo[b+1] if b < N-p-1 else N
    ans += p * ((r1-i)*(l1-l2) + (i-l1)*(r2-r1))
    insort(memo, i)

print(ans)


Fixed submission:
N = int(input())
P = list(map(int, input().split()))

I = [0] * N
for i in range(N):
    I[P[i]-1] = i

ans = 0
L = [i for i in range(-1, N-1)]
R = [i for i in range(1, N+1)]

for p in range(1,N+1):
    i = I[p-1]

    if R[i] < N:
        L[R[i]] = L[i]
    if L[i] >= 0:
        R[L[i]] = R[i]

    l1 = L[i]
    l2 = L[l1] if l1 >= 0 else -1
    r1 = R[i]
    r2 = R[r1] if r1 < N else N
    ans += p * ((r1-i)*(l1-l2) + (i-l1)*(r2-r1))

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(int, input().split()))

I = [0] * N
for i in range(N):
    I[P[i]-1] = i

ans = 0
memo = [I[N-1]]

for p in range(N-1, 0, -1):
    i = I[p-1]
    l1, l2 = 0, 0
    r1, r2 = N-1, N-1
    for j in range(i-1, -1, -1):
        if j in memo:
            l1 = j
            break
    else:
        l1 = -1
    for j in range(l1-1, -1, -1):
        if j in memo:
            l2 = j
            break
    else:
        l2 = -1
    for j in range(i+1, N):
        if j in memo:
            r1 = j
            break
    else:
        r1 = N
    for j in range(r1+1, N):
        if j in memo:
            r2 = j
            break
    else:
        r2 = N
    ans += p * ((r1-i)*(l1-l2) + (i-l1)*(r2-r1))
    memo.append(i)

print(ans)


Fixed submission:
N = int(input())
P = list(map(int, input().split()))

I = [0] * N
for i in range(N):
    I[P[i]-1] = i

ans = 0
L = [i for i in range(-1, N-1)]
R = [i for i in range(1, N+1)]

for p in range(1,N+1):
    i = I[p-1]

    if R[i] < N:
        L[R[i]] = L[i]
    if L[i] >= 0:
        R[L[i]] = R[i]

    l1 = L[i]
    l2 = L[l1] if l1 >= 0 else -1
    r1 = R[i]
    r2 = R[r1] if r1 < N else N
    ans += p * ((r1-i)*(l1-l2) + (i-l1)*(r2-r1))

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
from collections import deque
input = sys.stdin.readline
N, H, W = map(int, input().split())
RCA = []

class UF(object):
    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, v):
        if v == self.parent[v]:
            return v
        else:
            self.parent[v] = self.root(self.parent[v])
            return self.parent[v]
    
    def unite(self, u, v):
        u, v = self.root(u), self.root(v)
        if (u == v):
            return
        self.parent[u] = v

for _ in range(N):
    r, c, a = map(int, input().split())
    r, c = r-1, c-1
    RCA.append((a, r, c))

RCA.sort(reverse=True)
RCA = deque(RCA)

uf = UF(H+W+1)  # r0, r1, ..., rH, c0, c1, ..., cW, loopflag

cnt, ans = 0, 0
while RCA and cnt < H+W:
    a, r, c = RCA.popleft()
    c += H
    if uf.root(r) == uf.root(c):
        if uf.root(r) == uf.root(H+W):  # loop?
            continue
        uf.unite(r, H+W)
    ans += a
    cnt += 1
    uf.unite(r, c)

print(ans)


Fixed submission:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
N, H, W = map(int, input().split())
RCA = []

class UF(object):
    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, v):
        if v == self.parent[v]:
            return v
        else:
            self.parent[v] = self.root(self.parent[v])
            return self.parent[v]
    
    def unite(self, u, v):
        u, v = self.root(u), self.root(v)
        if (u == v):
            return
        self.parent[u] = v

for _ in range(N):
    r, c, a = map(int, input().split())
    r, c = r-1, c-1
    RCA.append((a, r, c))

RCA.sort(reverse=True)
RCA = deque(RCA)

uf = UF(H+W+1)  # r0, r1, ..., rH, c0, c1, ..., cW, loopflag

cnt, ans = 0, 0
while RCA and cnt < H+W:
    a, r, c = RCA.popleft()
    c += H
    if uf.root(r) == uf.root(c):
        if uf.root(r) == uf.root(H+W):  # loop?
            continue
        uf.unite(r, H+W)
    ans += a
    cnt += 1
    uf.unite(r, c)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
T = input()
LS = len(S)
LT = len(T)

dp = [0] * (LT+1)
dp[0] = -1
valid = True

for i in range(1,LT+1):
    t = T[i-1]
    p = (dp[i-1] + 1) % LS
    f = False  # find or not
    for j in range(p, LS):
        if S[j] == t:
            dp[i] = dp[i-1] + j - p + 1
            f = True
            break
    if f:
        continue
    for j in range(p):
        if S[j] == t:
            dp[i] = dp[i-1] + (LS - p) + j + 1
            f = True
            break
    if f:
        continue
    valid = False
    break
    
print(dp[-1] + 1 if valid else -1)


Fixed submission:
from bisect import bisect
S = input()
T = input()
LS = len(S)
LT = len(T)

H = {chr(i): [] for i in range(ord('a'), ord('z')+1)}
for i, s in enumerate(S):
    H[s].append(i)

dp = [0] * (LT+1)
dp[0] = -1
valid = True

for i in range(1,LT+1):
    t = T[i-1]
    p = dp[i-1] % LS if i > 1 else -1
    if len(H[t]) == 0:
        valid = False
        break
    q = bisect(H[t], p)
    if q == len(H[t]):
        dp[i] = dp[i-1] + LS - p + H[t][0]
    else:
        dp[i] = dp[i-1] + H[t][q] - p

print(dp[-1] + 1 if valid else -1)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0 for _ in range(13)]
dp[0] = 1
for i in range(N):
    pp = dp.copy()
    dp = [0 for _ in range(13)]
    s = S[N-i-1]
    b = pow(10, i, 13)
    if s == '?':
        for d in range(13):
            for e in range(10):
                dp[(d+b*e)%13] += pp[d]
                dp[(d+b*e)%13] %= MOD
    else:
        s = int(s)
        for d in range(13):
            dp[(d+b*s)%13] += pp[d]
            dp[(d+b*s)%13] %= MOD

print(dp[5])


Fixed submission:
S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0 for _ in range(13)]
pp = [0 for _ in range(13)]

dp[0] = 1
for i in range(N):
    pp, dp = dp, pp
    for d in range(13):
        dp[d] = 0
    s = S[N-i-1]
    b = pow(10, i, 13)
    if s == '?':
        for d in range(13):
            for e in range(10):
                dp[(d+b*e)%13] += pp[d]
                dp[(d+b*e)%13] %= MOD
    else:
        s = int(s)
        for d in range(13):
            dp[(d+b*s)%13] += pp[d]
            dp[(d+b*s)%13] %= MOD

print(dp[5])

Buggy python submission (verdict: Runtime Error):
S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0 for _ in range(13)]
dp[0] = 1
for i in range(N):
    pp = dp.copy()
    dp = [0 for _ in range(13)]
    s = S[N-i-1]
    b = pow(10, i, 13)
    if s == '?':
        for d in range(13):
            for e in range(10):
                dp[(d+b*e)%13] += pp[d]
                dp[(d+b*e)%13] %= MOD
    else:
        s = int(s)
        for d in range(13):
            dp[(d+b*s)%13] += pp[d]
            dp[(d+b*s)%13] %= MOD

print(dp[5])


Fixed submission:
S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0 for _ in range(13)]
pp = [0 for _ in range(13)]

dp[0] = 1
for i in range(N):
    pp, dp = dp, pp
    for d in range(13):
        dp[d] = 0
    s = S[N-i-1]
    b = pow(10, i, 13)
    if s == '?':
        for d in range(13):
            for e in range(10):
                dp[(d+b*e)%13] += pp[d]
                dp[(d+b*e)%13] %= MOD
    else:
        s = int(s)
        for d in range(13):
            dp[(d+b*s)%13] += pp[d]
            dp[(d+b*s)%13] %= MOD

print(dp[5])
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
N = int(input())
A = list(int(input()) for _ in range(N))
INF = 10 ** 9 + 1
V = [False for i in range(N)]
nv = 0
cnt = 0
while nv < N:
    dp = [INF]
    for i, a in enumerate(A):
        if V[i]:
            continue
        if a > dp[-1]:
            dp.append(a)
        else:
            j = bisect_left(dp, a)
            dp[j] = a
    nv += len(dp)
    dp.append(INF)
    m = len(dp)
    for i in range(N-1, -1, -1):
        if V[i]:
            continue
        if dp[m-1] <= A[i] < dp[m]:
            V[i] = True
            m -= 1
    cnt += 1

print(cnt)


Fixed submission:
from bisect import bisect_right
N = int(input())
A = list(int(input()) for _ in range(N))
INF = 10 ** 9 + 1

dp = [INF]
for a in A:
    if -a >= dp[-1]:
        dp.append(-a)
    else:
        j = bisect_right(dp, -a)
        dp[j] = -a

print(len(dp))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

memo = dict()
def dfs(l, r, wl, wr):
    if r <= l + 1:
        return 0
    if memo.get((l, r, wl, wr)):
        return memo[(l, r, wl, wr)]
    v = min(dfs(l, m, wl, wl+wr) + dfs(m, r, wl+wr, wr) + A[m] * (wl+wr) for m in range(l+1, r))
    memo[(l, r, wl, wr)] = v
    return v

print(dfs(0, N-1, 1, 1) + A[0] + A[N-1])


Fixed submission:
from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))

@lru_cache(maxsize=None)
def dfs(l, r, wl, wr):
    if r <= l + 1:
        return 0
    v = min(dfs(l, m, wl, wl+wr) + dfs(m, r, wl+wr, wr) + A[m] * (wl+wr) for m in range(l+1, r))
    return v

print(dfs(0, N-1, 1, 1) + A[0] + A[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

def dfs(l, r, wl, wr):
    if r <= l + 1:
        return 0
    return min(dfs(l, m, wl, wl+wr) + dfs(m, r, wl+wr, wr) + A[m] * (wl+wr) for m in range(l+1, r))

print(dfs(0, N-1, 1, 1) + A[0] + A[N-1])


Fixed submission:
from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))

@lru_cache(maxsize=None)
def dfs(l, r, wl, wr):
    if r <= l + 1:
        return 0
    v = min(dfs(l, m, wl, wl+wr) + dfs(m, r, wl+wr, wr) + A[m] * (wl+wr) for m in range(l+1, r))
    return v

print(dfs(0, N-1, 1, 1) + A[0] + A[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

def dfs(l, r, wl, wr):
    if r <= l + 1:
        return 0
    return min(dfs(l, m, wl, wl+wr) + dfs(m, r, wl+wr, wr) + A[m] * (wl+wr) for m in range(l+1, r))

print(dfs(0, N-1, 1, 1) + A[0] + A[N-1])


Fixed submission:
from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))

@lru_cache(maxsize=None)
def dfs(l, r, wl, wr):
    if r <= l + 1:
        return 0
    v = min(dfs(l, m, wl, wl+wr) + dfs(m, r, wl+wr, wr) + A[m] * (wl+wr) for m in range(l+1, r))
    return v

print(dfs(0, N-1, 1, 1) + A[0] + A[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 5)
MOD = 10 ** 9 + 7
N, K = map(int, input().split())
V = {i: [] for i in range(1,N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)

def dfs(u, p, c):
    l = len([i for i in V[u] if i != p])
    n = K - 2
    if p == 0:
        n += 1
    if l == 0:
        return c
    for v in V[u]:
        if v == p:
            continue
        c *= dfs(v, u, n)
        n -= 1
        c %= MOD
    return c

print(dfs(1, 0, K))


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 5)
MOD = 10 ** 9 + 7
N, K = map(int, input().split())
V = {i: [] for i in range(1,N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)

def dfs(u, p, c):
    l = len([i for i in V[u] if i != p])
    n = K - 2
    if p == 0:
        n += 1
    if l == 0:
        return c
    for v in V[u]:
        if v == p:
            continue
        c *= dfs(v, u, n)
        n -= 1
        c %= MOD
    return c

print(dfs(1, 0, K))
Buggy python submission (verdict: Runtime Error):
S = input()

print('Yes' if all(S.count(s) == 2 for s in input()) else 'No')


Fixed submission:
S = input()

print('Yes' if all(S.count(s) == 2 for s in S) else 'No')