Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def insertionSort(A, n, g, cnt):
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j + g] = A[j]
            j -= g
            cnt += 1
        A[j + g] = v
    return cnt
def shellSort(A, n):
    cnt = 0
    h = 1
    G = []
    while h < n:
        G += [h]
        h = 3 * h + 1
    m = len(G)
    for i in range(m - 1, -1, -1):
        cnt = insertionSort(A, n, G[i], cnt)
    print(m)
    print(*G[::-1])
    print(cnt)
    print(*A, sep="\n")
n = int(input())
A = [int(readline()) for _ in range(n)]
shellSort(A, n)


Fixed submission:
import sys
readline = sys.stdin.readline
def insertionSort(A, n, g, cnt):
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j + g] = A[j]
            j -= g
            cnt += 1
        A[j + g] = v
    return cnt
def shellSort(A, n):
    cnt = 0
    h = 4
    G = [1]
    while h < n:
        G += [h]
        h = 3 * h + 1
    m = len(G)
    for i in range(m - 1, -1, -1):
        cnt = insertionSort(A, n, G[i], cnt)
    print(m)
    print(*G[::-1])
    print(cnt)
    print(*A, sep="\n")
n = int(input())
# A = [int(readline()) for _ in range(n)]
A = list(map(int, sys.stdin))
shellSort(A, n)
Buggy python submission (verdict: Runtime Error):
import sys
from collections import deque
readline = sys.stdin.readline
dq = deque()
for _ in range(int(input())):
    ss = readline()
    if ss == "deleteFirst":
        del dq[0]
    elif ss == "deleteLast":
        del dq[-1]
    else:
        c, s = ss.split()
        s = int(s)
        if c == "insert":
            dq.appendleft(s)
        elif c == "delete":
            if s in dq:
                dq.remove(s)
print(*dq)



Fixed submission:
import sys
from collections import deque
readline = sys.stdin.readline
dq = deque()
for _ in range(int(input())):
    c = readline().split()
    if c[0] == "deleteFirst":
        dq.popleft()
    elif c[0] == "deleteLast":
        dq.pop()
    else:
        if c[0] == "insert":
            dq.appendleft(c[1])
        elif c[0] == "delete":
            if c[1] in dq:
                dq.remove(c[1])
print(*dq)
Buggy python submission (verdict: Time Limit Exceeded):
li = []
for _ in range(int(input())):
    c, s = input().split()
    if c == "insert":
        li.append(s)
    elif c == "find":
        print("yes" if s in li else "no")


Fixed submission:
import sys
readline = sys.stdin.readline
SET = set()
input()
for s in sys.stdin:
    if s[0] == "i":
        SET.add(s[7:])
    elif s[0] == "f":
        print("yes" if s[5:] in SET else "no")

Buggy python submission (verdict: Time Limit Exceeded):
li = []
for _ in range(int(input())):
    c, s = input().split()
    if c == "insert":
        li.append(s)
    elif c == "find":
        print("yes" if s in li else "no")


Fixed submission:
import sys
readline = sys.stdin.readline
SET = set()
input()
for s in sys.stdin:
    if s[0] == "i":
        SET.add(s[7:])
    elif s[0] == "f":
        print("yes" if s[5:] in SET else "no")

Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.readline
li = []
for _ in range(int(readline())):
    c, s = readline().split()
    if c == "insert":
        li.append(s)
    elif c == "find":
        print("yes" if s in li else "no")



Fixed submission:
import sys
readline = sys.stdin.readline
SET = set()
input()
for s in sys.stdin:
    if s[0] == "i":
        SET.add(s[7:])
    elif s[0] == "f":
        print("yes" if s[5:] in SET else "no")
Buggy python submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline
N, K = map(int, input().split())
W = tuple(int(readline()) for _ in range(n))
ma = max(W)
def check(x):
    if x < ma:
        return False
    use = 1
    rest = x
    for w in W:
        if rest >= w:
            rest -= w
        else:
            rest = x - w
            use += 1
    return use <= K
l = 0
r = sum(W)
while r - l > 1:
    m = (r + l) // 2
    if check(m):
        r = m
    else:
        l = m
print(r)


Fixed submission:
import sys
readline = sys.stdin.readline
N, K = map(int, input().split())
W = tuple(map(int, sys.stdin.readlines()))
ma = max(W)
def check(x):
    if x < ma:
        return False
    use = 1
    rest = x
    for w in W:
        if rest >= w:
            rest -= w
        else:
            rest = x - w
            use += 1
            if use > K:
                return False
    return True
l = 0
r = sum(W)
while r - l > 1:
    m = (r + l) // 2
    if check(m):
        r = m
    else:
        l = m
print(r)

Buggy python submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline
N, K = map(int, input().split())
W = {map(int, sys.stdin.read().splitlines())}
ma = max(W)
def check(x):
    if x < ma:
        return False
    use = 1
    rest = x
    for w in W:
        if rest >= w:
            rest -= w
        else:
            rest = x - w
            use += 1
    return use <= K
l = 0
r = sum(W)
while r - l > 1:
    m = (r + l) // 2
    if check(m):
        r = m
    else:
        l = m
print(r)


Fixed submission:
import sys
readline = sys.stdin.readline
N, K = map(int, input().split())
W = tuple(map(int, sys.stdin.readlines()))
ma = max(W)
def check(x):
    if x < ma:
        return False
    use = 1
    rest = x
    for w in W:
        if rest >= w:
            rest -= w
        else:
            rest = x - w
            use += 1
            if use > K:
                return False
    return True
l = 0
r = sum(W)
while r - l > 1:
    m = (r + l) // 2
    if check(m):
        r = m
    else:
        l = m
print(r)

Buggy python submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline
N, K = map(int, input().split())
W = tuple(map(int, sys.stdin.splitlines()))
ma = max(W)
def check(x):
    if x < ma:
        return False
    use = 1
    rest = x
    for w in W:
        if rest >= w:
            rest -= w
        else:
            rest = x - w
            use += 1
    return use <= K
l = 0
r = sum(W)
while r - l > 1:
    m = (r + l) // 2
    if check(m):
        r = m
    else:
        l = m
print(r)


Fixed submission:
import sys
readline = sys.stdin.readline
N, K = map(int, input().split())
W = tuple(map(int, sys.stdin.readlines()))
ma = max(W)
def check(x):
    if x < ma:
        return False
    use = 1
    rest = x
    for w in W:
        if rest >= w:
            rest -= w
        else:
            rest = x - w
            use += 1
            if use > K:
                return False
    return True
l = 0
r = sum(W)
while r - l > 1:
    m = (r + l) // 2
    if check(m):
        r = m
    else:
        l = m
print(r)
Buggy python submission (verdict: Runtime Error):
from itertools import combinations
n = int(input())
A = tuple(map(int, input().split()))
def solve(m):
    if m in A:
        return "yes"
    for i in range(2, n + 1):
        for C in combinations(A, i):
            if sum(C) == m:
                return "yes"
    return "no"
q = int(input())
for m in map(int, input().split()):
    print(solve(m))



Fixed submission:
n = int(input())
SET1 = {0}
for a in map(int, input().split()):
    for b in tuple(SET1):
        SET1.add(a + b)
input()
for m in map(int, input().split()):
    print('yes' if m in SET1 else 'no')

Buggy python submission (verdict: Runtime Error):
from itertools import combinations
n = int(input())
A = tuple(map(int, input().split()))
SET = set(A)
def solve(m):
    if m in A:
        return "yes"
    for i in range(1, n):
        for C in combinations(A, i):
            sumC = sum(C)
            if sumC < m and m - sumC in SET - set(C):
                return "yes"
    return "no"
q = int(input())
for m in map(int, input().split()):
    print(solve(m))



Fixed submission:
n = int(input())
SET1 = {0}
for a in map(int, input().split()):
    for b in tuple(SET1):
        SET1.add(a + b)
input()
for m in map(int, input().split()):
    print('yes' if m in SET1 else 'no')

Buggy python submission (verdict: Runtime Error):
from itertools import combinations
n = int(input())
A = tuple(map(int, input().split()))
SET = set(A)
def solve(m):
    if m in A:
        return "yes"
    dp = [0]
    for a in A:
        q = []
        for d in dp:
            q.append(d)
            q.append(d + a)
        dp = q
    if m in dp:
        return "yes"
    return "no"
q = int(input())
for m in map(int, input().split()):
    print(solve(m))



Fixed submission:
n = int(input())
SET1 = {0}
for a in map(int, input().split()):
    for b in tuple(SET1):
        SET1.add(a + b)
input()
for m in map(int, input().split()):
    print('yes' if m in SET1 else 'no')
Buggy python submission (verdict: Runtime Error):
def partition(p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1
n = int(input())
A = [int(i) for i in input().split()]
q = partition(0, n - 1);
print(*A[:q], "[" + str(A[q]) + "]", end="")
if len(A[q + 1:]) > 0:
    print("", *A[q + 1:])
else:
    print("")

Fixed submission:
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1
n = int(input())
A = list(map(int, input().split()))
p = partition(A, 0, n - 1)
A[p] = f"[{A[p]}]"
print(*A)

Buggy python submission (verdict: Runtime Error):
def partition(p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1
n = int(input())
A = [int(i) for i in input().split()]
q = partition(0, n - 1);
print(*A[:q], "[" + str(A[q]) + "]", end="")
if len(A[q + 1:]) > 0:
    print("", *A[q + 1:])

Fixed submission:
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1
n = int(input())
A = list(map(int, input().split()))
p = partition(A, 0, n - 1)
A[p] = f"[{A[p]}]"
print(*A)

Buggy python submission (verdict: Runtime Error):
n = int(input())
A = [int(i) for i in input().split()]
def partition(p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1

q = partition(0, n - 1);
print(*A[:q], "[" + str(A[q]) + "]", end="")
if len(A[q + 1:]) > 0:
    print("", *A[q + 1:])

Fixed submission:
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1
n = int(input())
A = list(map(int, input().split()))
p = partition(A, 0, n - 1)
A[p] = f"[{A[p]}]"
print(*A)

Buggy python submission (verdict: Runtime Error):
n = int(input())
A = [int(i) for i in input().split()]
def partition(p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1

q = partition(0, n - 1)
print(*A[:q], "[" + str(A[q]) + "]", end="")
if len(A[q + 1:]) > 0:
    print("", *A[q + 1:])

Fixed submission:
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1
n = int(input())
A = list(map(int, input().split()))
p = partition(A, 0, n - 1)
A[p] = f"[{A[p]}]"
print(*A)
Buggy python submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline
def partition(A, p, r):
    x = A[r][1]
    i = p - 1
    for j in range(p, r):
        if A[j][1] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1
def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)
def isStable(A):
    for i in range(0, len(A) - 1):
        if A[i][1] == A[i + 1][1]:
            if A[i][2] > A[i + 1][2]:
                return False
    return True
n = int(input())
f = lambda a: (a[0], int(a[1]))
A = [f(readline().split()) + (i) for i in range(n)]
quicksort(A, 0, n - 1)
print("Stable" if isStable(A) else "Not stable")
print("\n".join(f"{a} {b}" for a, b, c in A))



Fixed submission:
import sys
readline = sys.stdin.readline
def partition(A, p, r):
    x = A[r][1]
    i = p - 1
    for j in range(p, r):
        if A[j][1] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1
def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)
def isStable(A):
    for i in range(0, len(A) - 1):
        if A[i][1] == A[i + 1][1]:
            if A[i][2] > A[i + 1][2]:
                return "Not stable"
    return "Stable"
n = int(input())
f = lambda a, i: (a[0], int(a[1]), i)
A = [f(readline().split(), i) for i in range(n)]
quicksort(A, 0, n - 1)
print(isStable(A))
print("\n".join(f"{a} {b}" for a, b, c in A))
Buggy python submission (verdict: Runtime Error):
n = int(input())
A = list(map(int, input().split()))
s = min(A)
def solve():
    ans = 0
    V = [False] * n
    # B = sorted(A)
    # T = {B[i]: i for i in range(n)}
	T = {B: i for i, B in enumerate(sorted(A))}
    for i in range(n):
        if V[i]:
            continue
        cur = i
        S = an = 0
        m = 10000
        while not V[cur]:
            V[cur] = True
            an += 1
            v = A[cur]
            m = min(m, v)
            S += v
            cur = T[v]
        ans += min(S + (an - 2) * m, m + S + (an + 1) * s)
    return ans
print(solve())



Fixed submission:
n = int(input())
A = list(map(int, input().split()))
s = min(A)
def solve():
    ans = 0
    V = [False] * n
    B = sorted(A)
    T = {B[i]: i for i in range(n)}
    for i in range(n):
        if V[i]:
            continue
        cur = i
        S = an = 0
        m = 10000
        while not V[cur]:
            V[cur] = True
            an += 1
            v = A[cur]
            m = min(m, v)
            S += v
            cur = T[v]
        ans += min(S + (an - 2) * m, m + S + (an + 1) * s)
    return ans
print(solve())
Buggy python submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline
class Tree:
    __slots__ = ['id', 'p', 'sibling', 'degree', 'depth', 'height', 'type', 'c']
    def __init__(self, id):
        self.id = id
        self.p = -1
        self.sibling = -1
        self.degree = 0
        self.depth = 0
        self.height = 0
        self.type = "leaf"
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, sibling = {self.sibling}, degree = {self.degree}, depth = {self.depth}, height = {self.height}, {self.type}"
def solve():
    n = int(input())
    tree = tuple(Tree(i) for i in range(n))
    for _ in range(n):
        id, *c = map(int, readline().replace("-1", "").split())
        if c != []:
            tree[id].type = "internal node"
            tree[id].c = c
            for j in c:
                tree[j].p = id
            len_c = len(c)
            tree[id].degree = len_c
            if len_c == 2:
                tree[c[0]].sibling = c[1]
                tree[c[1]].sibling = c[0]
    rootget = lambda x: rootget(x) if tree[x].p != -1 else x
    root = rootget(0)
    tree[root].type = "root"
    def depth_height_check(id, d):
        d += 1
        height = 0
        for i in tree[id].c:
            tree[i].depth = d
            if tree[i].type != "leaf":
                tree[i].height = depth_height_check(i, d) + 1
                height = max(height, tree[i].height)
        return height
    tree[root].height = depth_height_check(root, 0) + 1 if n > 1 else 0
    print("\n".join(map(str, tree)))
solve()



Fixed submission:
import sys
readline = sys.stdin.readline
class Tree:
    __slots__ = ['id', 'p', 'sibling', 'degree', 'depth', 'height', 'type', 'c']
    def __init__(self, id):
        self.id = id
        self.p = -1
        self.sibling = -1
        self.degree = 0
        self.depth = 0
        self.height = 0
        self.type = "leaf"
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, sibling = {self.sibling}, degree = {self.degree}, depth = {self.depth}, height = {self.height}, {self.type}"
n = int(input())
tree = tuple(Tree(i) for i in range(n))
for _ in range(n):
    id, *c = (i for i in map(int, readline().split()) if i != -1)
    if c != []:
        tree[id].type = "internal node"
        tree[id].c = c
        for j in c:
            tree[j].p = id
        len_c = len(c)
        tree[id].degree = len_c
        if len_c == 2:
            tree[c[0]].sibling = c[1]
            tree[c[1]].sibling = c[0]
root = 0
while tree[root].p != -1:
    root = tree[root].p
tree[root].type = "root"
def depth_height_check(id, d):
    d += 1
    height = 0
    for i in tree[id].c:
        tree[i].depth = d
        if tree[i].type != "leaf":
            tree[i].height = depth_height_check(i, d)
            height = max(height, tree[i].height)
    return height + 1
tree[root].height = depth_height_check(root, 0) if n > 1 else 0
print("\n".join(map(str, tree)))
Buggy python submission (verdict: Runtime Error):
class Node():
    key = 0
    l = None
    r = None
    def __init__(self, key):
        self.key = key
T = [] * int(5e6)
def insert(z):
    if z == 0: return
    y = None
    x = 0
    while x is not None:
        y = x
        x = (T[x].l if T[z].key < T[x].key else  T[x].r)
    if T[z].key < T[y].key: T[y].l = z
    else: T[y].r = z
def inorder(x):
    if x == None: return;
    inorder(T[x].l);
    print("", T[x].key, end="")
    inorder(T[x].r);
def preorder(x):
    if x == None: return;
    print("", T[x].key, end="")
    preorder(T[x].l);
    preorder(T[x].r);
n = int(input())
for i in range(n):
    s = input()
    if s == "print":
        inorder(0)
        print()
        preorder(0)
        print()
    else:
        x = int(s.split()[1])
        T.append(Node(x))
        insert(i)

Fixed submission:
import sys
readline = sys.stdin.readline
NIL = None
class Tree:
    __slots__ = ['key', 'p', 'left', 'right']
    def __init__(self, key = None):
        self.key = key
        self.p = NIL
        self.left = NIL
        self.right = NIL
n = int(input())
tree = {"root":NIL}
def insert(T, z):
    y = NIL
    x = T["root"]
    while x != NIL:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.p = y
    if y == NIL:
        T["root"] = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z
def preorder_tree_walk(T):
    print(f" {T.key}", end="")
    if T.left != NIL:
        preorder_tree_walk(T.left)
    if T.right != NIL:
        preorder_tree_walk(T.right)
def inorder_tree_walk(T):
    if T.left != NIL:
        inorder_tree_walk(T.left)
    print(f" {T.key}", end="")
    if T.right != NIL:
        inorder_tree_walk(T.right)
for _ in range(n):
    ss = readline()
    if ss[0] == "i":
        s, v = ss.split()
        insert(tree, Tree(int(v)))
    else:
        inorder_tree_walk(tree["root"])
        print()
        preorder_tree_walk(tree["root"])
        print()
Buggy python submission (verdict: Runtime Error):
import sys
h, w = map(int, sys.stdin.readline().split())
dp = [[0] * w for _ in range(h)]
G = [list(map(int, i.split())) for i in sys.stdin.readlines()]
for x in range(h):
    dp[x][0] = 1 if G[x][0] == 0 else 0
for y in range(w):
    dp[0][y] = 1 if G[0][y] == 0 else 0
for i in range(1, h):
    for j in range(1, w):
        if(G[i][j] == 0):
            dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
print(max(sum(dp, []) ** 2)

Fixed submission:
import sys
import itertools
h, w = map(int, sys.stdin.readline().split())
dp = [[0] * w for _ in range(h)]
G = [[int(j) for j in sys.stdin.readline().split()] for _ in range(h)]
for x in range(h):
    dp[x][0] = 1 if G[x][0] == 0 else 0
for y in range(w):
    dp[0][y] = 1 if G[0][y] == 0 else 0
for i in range(1, h):
    for j in range(1, w):
        if(G[i][j] == 0):
            dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
print(max(max(i) for i in dp) ** 2)

Buggy python submission (verdict: Runtime Error):
import sys
h, w = map(int, sys.stdin.readline().split())
dp = [[0] * w for _ in range(h)]
G = [list(map(int, i.split())) for i in sys.stdin.readlines()]
for x in range(h):
    dp[x][0] = 1 if G[x][0] == 0 else 0
for y in range(w):
    dp[0][y] = 1 if G[0][y] == 0 else 0
for i in range(1, h):
    for j in range(1, w):
        if(G[i][j] == 0):
            dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
print(max(sum(dp, []) ** 2))

Fixed submission:
import sys
import itertools
h, w = map(int, sys.stdin.readline().split())
dp = [[0] * w for _ in range(h)]
G = [[int(j) for j in sys.stdin.readline().split()] for _ in range(h)]
for x in range(h):
    dp[x][0] = 1 if G[x][0] == 0 else 0
for y in range(w):
    dp[0][y] = 1 if G[0][y] == 0 else 0
for i in range(1, h):
    for j in range(1, w):
        if(G[i][j] == 0):
            dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
print(max(max(i) for i in dp) ** 2)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
h, w = map(int, sys.stdin.readline().split())
dp = [[0] * w for _ in range(h)]
G = [list(map(int, i.split())) for i in sys.stdin.readlines()]
for x in range(h):
    dp[x][0] = 1 if G[x][0] == 0 else 0
for y in range(w):
    dp[0][y] = 1 if G[0][y] == 0 else 0
for i in range(1, h):
    for j in range(1, w):
        if(G[i][j] == 0):
            dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
print(max(sum(dp, [])) ** 2)

Fixed submission:
import sys
import itertools
h, w = map(int, sys.stdin.readline().split())
dp = [[0] * w for _ in range(h)]
G = [[int(j) for j in sys.stdin.readline().split()] for _ in range(h)]
for x in range(h):
    dp[x][0] = 1 if G[x][0] == 0 else 0
for y in range(w):
    dp[0][y] = 1 if G[0][y] == 0 else 0
for i in range(1, h):
    for j in range(1, w):
        if(G[i][j] == 0):
            dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
print(max(max(i) for i in dp) ** 2)
Buggy python submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline
_input = sys.stdin.readlines()
if len(_input) < 2:
    print("In preparation.")
    exit()
n = int(_input[0])
li = list(map(int, _input[1]))
def largest_histogram(histogram):
    if len(histogram) == 0: return 0
    histogram = list(histogram)
    max_h = max(n, max(histogram))
    for i in range(n):
        for j in range(2, histogram[i] + 1):
            m = 1
            for k in range(i + 1, n):
                if histogram[k] >= j:
                    m += 1
                else:
                    break
            if max_h < j * m:
                max_h = j * m
    return max_h
print(largest_histogram(li))

Fixed submission:
import sys
from collections import deque
readline = sys.stdin.readline
n = int(readline())
li = list(map(int, readline().split()))
def square(P):
    G = []
    L = deque()
    for i, v in enumerate(P):
        if not L:
            L.append((i, v))
            continue
        if v > L[-1][1]:
            L.append((i, v))
        elif v < L[-1][1]:
            k = i - 1
            while L and v < L[-1][1]:
                a = L.pop()
                G.append((k - a[0] + 1) * a[1])
            L.append((a[0], v))
    while L:
        a = L.pop()
        G.append((n - a[0]) * a[1])
    return max(G)
print(square(li))