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

Fixed submission:
from collections import deque
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(-a)
pos = deque(sorted(pos))
neg = deque(sorted(neg))
mod = 10**9 + 7
ans = 1
sign = 1
if K % 2 == 1:
    if len(pos) > 0:
        ans = ans * pos.pop() % mod
    else:
        ans = ans * neg.popleft() % mod
        sign *= -1
    K -= 1
while K > 0:
    if len(pos) == 1 and len(neg) == 1:
        ans = ans * -neg.pop() * pos.pop() % mod
    elif sign == 1:
        if len(pos) < 2 or (len(neg) >= 2 and pos[-2] * pos[-1] < neg[-2] * neg[-1]):
            ans = ans * neg.pop() * neg.pop() % mod
        else:
            ans = ans * pos.pop() * pos.pop() % mod
    else:
        if len(pos) < 2 or (len(neg) >= 2 and pos[-2] * pos[-1] < neg[-2] * neg[-1]):
            ans = ans * neg.popleft() * neg.popleft() % mod
        else:
            ans = ans * pos.popleft() * pos.popleft() % mod
    K -= 2
ans = ans * sign % mod
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(-a)
pos = deque(sorted(pos))
neg = deque(sorted(neg))
mod = 10**9 + 7
ans = 1
sign = 1
if K % 2 == 1:
    if len(pos) > 0:
        ans = ans * pos.pop() % mod
    else:
        ans = ans * neg.popleft() % mod
        sign *= -1
    K -= 1
while K > 0:
    if len(pos) == 1 and len(neg) == 1:
        ans = ans * -neg.pop() * pos.pop() % mod
    if sign == 1:
        if len(pos) < 2 or (len(neg) >= 2 and pos[-2] * pos[-1] < neg[-2] * neg[-1]):
            ans = ans * neg.pop() * neg.pop() % mod
        else:
            ans = ans * pos.pop() * pos.pop() % mod
    else:
        if len(pos) < 2 or (len(neg) >= 2 and pos[-2] * pos[-1] < neg[-2] * neg[-1]):
            ans = ans * neg.popleft() * neg.popleft() % mod
        else:
            ans = ans * pos.popleft() * pos.popleft() % mod
    K -= 2
ans = ans * sign % mod
print(ans)
Problem p02640 (python)

Fixed submission:
X, Y = map(int, input().split())
for a in range(X+1):
    b = X - a
    if 2 * a + 4 * b == Y:
        print('Yes')
        exit()
print('No')

Buggy submission (verdict: Runtime Error):
X, Y = map(int, input().split())
for a in range(X+1):
    b = X - a
    if 2 * a + 4 * b == Y:
        print('Yes')
        exit()
print('No')X, Y = map(int, input().split())
for a in range(X+1):
    b = X - a
    if 2 * a + 4 * b == Y:
        print('Yes')
        exit()
print('No')
Problem p02698 (python)

Fixed submission:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
G = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append(v)
    G[v].append(u)
lis = [float('inf')] * N
ans = [0] * N
visited = [False] * N

def dfs(v):
    visited[v] = True
    i = bisect_left(lis, a[v])
    tmp = lis[i]
    lis[i] = a[v]
    ans[v] = bisect_left(lis, float('inf'))
    for c in G[v]:
        if visited[c]:
            continue
        dfs(c)
    lis[i] = tmp

dfs(0)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
from bisect import bisect_left
import sys
input = sys.stdin.readline

N = int(input())
a = [0] + list(map(int, input().split()))
G = [[] for _ in range(N+1)]
for _ in range(N-1):
    u, v = map(int, input().split())
    G[u].append(v)
    G[v].append(u)
lis = [float('inf')] * (N+1)
ans = [0] * (N+1)

def dfs(v, p):
    i = bisect_left(lis, a[v])
    ans[v] = i + 1
    tmp = lis[i]
    lis[i] = a[v]
    for c in G[v]:
        if c == p:
            continue
        dfs(c, v)
    lis[i] = tmp

dfs(1, 0)
print('\n'.join(map(str, ans[1:])))
Problem p02807 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)


def mod_inverse(n, mod=10**9+7):
    return pow(n, mod-2, mod)


def combination(n, k, mod=10**9+7):
    numer = denom = 1
    for i in range(k):
        numer = (numer * (n-i)) % mod
        denom = (denom * (i+1)) % mod
    return (numer * mod_inverse(denom, mod)) % mod


def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1) % mod


mod = 10**9+7
N = int(input())
x = [0] + list(map(int, input().split()))
fact = factorial(N-1)

ans = 0
for k in range(2, N):
    ans = (ans + x[k] * (1 - mod_inverse(k)))

for k in range(1, N-1):
    ans = (ans - x[k] * (1 - mod_inverse(N-k))) % mod

ans = ans * fact % mod

ans = (ans + fact * sum((x[N] - x[k]) * mod_inverse(N-k) for k in range(1, N))) % mod

print(ans)

Buggy submission (verdict: Runtime Error):
def mod_inverse(n, mod=10**9+7):
    return pow(n, mod-2, mod)


def combination(n, k, mod=10**9+7):
    numer = denom = 1
    for i in range(k):
        numer = (numer * (n-i)) % mod
        denom = (denom * (i+1)) % mod
    return (numer * mod_inverse(denom, mod)) % mod


def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1) % mod


mod = 10**9+7
N = int(input())
x = [0] + list(map(int, input().split()))
fact = factorial(N-1)

ans = 0
for k in range(2, N):
    ans = (ans + x[k] * (1 - mod_inverse(k)))

for k in range(1, N-1):
    ans = (ans - x[k] * (1 - mod_inverse(N-k))) % mod

ans = ans * fact % mod

ans = (ans + fact * sum((x[N] - x[k]) * mod_inverse(N-k) for k in range(1, N))) % mod

print(ans)
Problem p02813 (python)

Fixed submission:
def generate_perms(n, perms):
    if n == 0:
        return perms
    new_perms = []
    for perm in perms:
        for i in range(1, N+1):
            if i not in perm:
                p = list(perm)
                p.append(i)
                new_perms.append(p)
    return generate_perms(n-1, new_perms)


N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
perms = generate_perms(N, [[]])
print(abs(perms.index(P) - perms.index(Q)))

Buggy submission (verdict: Runtime Error):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;
    vector<int> P(N), Q(N);
    for (int i = 0; i < N; i++) cin >> P[i];
    for (int i = 0; i < N; i++) cin >> Q[i];
    vector<int> perm(N);
    for (int i = 0; i < N; i++) perm[i] = i + 1;
    int n = 0;
    int a, b;
    do {
        if (perm == P) a = n;
        if (perm == Q) b = n;
        n++;
    } while (next_permutation(perm.begin(), perm.end()));
    cout << abs(a - b) << endl;
}
Problem p02824 (python)

Fixed submission:
def check(n):
    x = A[n] + M
    if P == 1:
        B = A[:n] + A[n+1:]
    else:
        B = A[:n] + A[n+1:-(P-1)]
    scores = M * (V - P)
    if x < B[-1]:
        return False
    for b in B:
        if b + M <= x:
            scores -= M
        else:
            scores -= x - b
        if scores <= 0:
            return True
    return False


N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

left = 0
right = N - P
while left < right:
    mid = (left+right) // 2
    if check(mid):
        right = mid
    else:
        left = mid + 1
print(N - left)

Buggy submission (verdict: Runtime Error):
def check(n):
    x = A[n] + M
    B = A[:n] + A[n+1:-(P-1)]
    scores = M * (V - P)
    if x < B[-1]:
        return False
    for b in B:
        if b + M <= x:
            scores -= M
        else:
            scores -= x - b
        if scores <= 0:
            return True
    return False


N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
print(A)
left = 0
right = N - P
while left < right:
    mid = (left+right) // 2
    if check(mid):
        right = mid
    else:
        left = mid + 1
print(N - left)
Problem p02874 (python)

Fixed submission:
N = int(input())
LR = []
p = 0
max_L = 0
q = 0
min_R = 10**9 + 1

for i in range(N):
    L, R = map(int, input().split())
    R += 1
    LR.append((L, R))
    if L > max_L:
        p = i
        max_L = L
    if R < min_R:
        q = i
        min_R = R

ans1 = max(R - L for L, R in LR) + max(min_R - max_L, 0)

if N == 2:
    print(sum(R - L for L, R in LR))
    exit()

if p == q:
    print(ans1)
    exit()

L1, R1 = LR[p]
L2, R2 = LR[q]
LR = [(L, R) for i, (L, R) in enumerate(LR) if i != p and i != q]
LR.sort(key=lambda x: (x[1], x[0]), reverse=True)

n = len(LR) + 1
min_sr = [R1] * n
max_tl = [L2] * n

for i in range(1, n):
    min_sr[i] = min(min_sr[i-1], LR[i-1][1])
    max_tl[n-i-1] = max(max_tl[n-i], LR[n-i-1][0])

ans2 = max(max(r - L1, 0) + max(R2 - l, 0) for r, l in zip(min_sr, max_tl))

print(max(ans1, ans2))

Buggy submission (verdict: Runtime Error):
N = int(input())
LR = []
p = 0
max_L = 0
q = 0
min_R = 10**9 + 1

for i in range(N):
    L, R = map(int, input().split())
    R += 1
    LR.append((L, R))
    if L > max_L:
        p = i
        max_L = L
    if R < min_R:
        q = i
        min_R = R

if p == q:
    print(max(r - l for l, r in LR) + max(min_R - max_L, 0))
    exit()

L1, R1 = LR[p]
L2, R2 = LR[q]
LR = [(L, R) for i, (L, R) in enumerate(LR) if i != p and i != q]
LR.sort(key=lambda x: (x[1], x[0]), reverse=True)

ans1 = max(R - L for L, R in LR) + max(min_R - max_L, 0)

n = len(LR) + 1
min_sr = [R1] * n
max_tl = [L2] * n

for i in range(1, n):
    min_sr[i] = min(min_sr[i-1], LR[i-1][1])
    max_tl[n-i-1] = max(max_tl[n-i], LR[n-i-1][0])

ans2 = max(max(r - L1, 0) + max(R2 - l, 0) for r, l in zip(min_sr, max_tl))

print(max(ans1, ans2))

Buggy submission (verdict: Runtime Error):
def calc(s, t):
    t_l = [x[0] for x in t]
    s_r = [x[1] for x in s]
    return max(min(s_r) - max_L, 0) + max(min_R - max(t_l), 0)


N = int(input())
sections = []

L, R = map(int, input().split())
sections.append((L, R + 1))
p = 0
max_L = L
q = 0
min_R = R

for i in range(1, N):
    L, R = map(int, input().split())
    R += 1
    sections.append((L, R))
    if L > max_L:
        p = i
        max_L = L
    if R < min_R:
        q = i
        min_R = R

s = [sections[p]]
t = [sections[q]]
sections.pop(p)
sections.sort(key=lambda x: (x[1], x[0]))
sections.pop(0)  # q
s = sections + s

ranges = [x[1] - x[0] for x in sections]
ans1 = max(ranges) + max(min_R - max_L, 0)

ans2 = calc(s, t)

for i in range(len(sections)):
    t += [s.pop(0)]
    ans2 = max(ans2, calc(s, t))

print(max(ans1, ans2))
Problem p02883 (python)

Fixed submission:
import numpy as np

N, K = map(int, input().split())
A = np.array(input().split(), np.int64)
F = np.array(input().split(), np.int64)
A.sort()
F.sort()
F = F[::-1]

l = 0
r = (A * F).max()

while l < r:
    m = (l + r) // 2
    if np.maximum(A - m // F, 0).sum() <= K:
        r = m
    else:
        l = m + 1

print(r)

Buggy submission (verdict: Runtime Error):
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))
    A.sort()
    F.sort(reverse=True)
     
    l = 0
    r = max(a * f for a, f in zip(A, F))
     
    while l < r:
        m = (l + r) // 2
        if sum(max(a - m // f, 0) for a, f in zip(A, F)) <= K:
            r = m
        else:
            l = m + 1
     
    print(r)
Problem p02886 (python)

Fixed submission:
N = int(input())
d = list(map(int, input().split()))
sum = 0
for i in range(N):
    for j in range(i+1, N):
        sum += d[i] * d[j]
print(sum)

Buggy submission (verdict: Runtime Error):
N = int(input())
d = map(int, input().split())
print(sum(d[i] * d[j] for j in range(i+1, len(d)) for i in range(len(d))))
Problem p02936 (python)

Fixed submission:
from collections import defaultdict, deque

N, Q = map(int, input().split())
tree = defaultdict(list)
counter = [0] * N
for i in range(N-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

for j in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x

visited = [False] * N

queue = deque()
queue.append(0)
while queue:
    parent = queue.popleft()
    visited[parent] = True
    for child in tree[parent]:
        if not visited[child]:
            counter[child] += counter[parent]
            queue.append(child)

print(' '.join(map(str, counter)))

Buggy submission (verdict: Runtime Error):
from collections import defaultdict

N, Q = map(int, input().split())
tree = defaultdict(list)
counter = [0] * N
for i in range(N-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

for j in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x

visited = [False] * N


def dfs(parent):
    visited[parent] = True
    for child in tree[parent]:
        if not visited[child]:
            counter[child] += counter[parent]
            dfs(child)


dfs(0)
print(' '.join(map(str, counter)))
Problem p02953 (python)

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

N = int(input())
H = list(map(int, input().split()))
prev = -1
for h in H:
    if prev > h:
        print('No')
        exit()
    if prev <= h - 1:
        prev = h - 1
    else:
        prev = h
print('Yes')

Buggy submission (verdict: Runtime Error):
#![allow(non_snake_case)]

fn read_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn read_vec() -> Vec<i32> {
    read_line()
        .split_whitespace()
        .map(|e| e.parse().unwrap())
        .collect()
}

fn main() {
    let N: usize = read_line().parse().unwrap();
    let H = read_vec();
    let mut prev = 0;
    for h in H {
        if prev < h {
            prev = h - 1;
        } else if prev > h {
            println!("No");
            return;
        }
    }
    println!("Yes");
}
Problem p02991 (python)

Fixed submission:
from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    G[u].append(v)
S, T = map(int, input().split())
queue = deque()
queue.append((S, 0))
visited = [[False] * 3 for _ in range(N+1)]
while queue:
    u, d = queue.popleft()
    if visited[u][d % 3]:
        continue
    visited[u][d % 3] = True
    if d % 3 == 0 and u == T:
        print(d // 3)
        exit()
    for v in G[u]:
        queue.append((v, d+1))
print(-1)

Buggy submission (verdict: Runtime Error):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline


def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance


N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    G[u].append(v)
S, T = map(int, input().split())
G2 = [[] for _ in range(N+1)]


def dfs(nodes, v):
    if nodes[0] != -1:
        if (v, 1) in G2[nodes[0]]:
            return
        G2[nodes[0]].append((v, 1))
    for u in G[v]:
        dfs(nodes[1:] + [v], u)


dfs([-1] * 3, S)
dist = dijkstra(G2, N+1, S)
print(dist[T] if dist[T] != float('inf') else -1)
Problem p03008 (python)

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

N = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())
INF = 10**18
A = [INF] * 3
B = [INF] * 3
values = [abs(ga - gb), abs(sa - sb), abs(ba - bb)]
if ga < gb:
    A[0] = ga
elif ga > gb:
    B[0] = gb
if sa < sb:
    A[1] = sa
elif sa > sb:
    B[1] = sb
if ba < bb:
    A[2] = ba
elif ba > bb:
    B[2] = bb

def calc(X):
    dp = [0] * (N+1)
    dp[0] = 0
    for x, v in zip(X, values):
        for i in range(N+1-x):
            dp[i+x] = max(dp[i+x], dp[i] + v)
    return dp[-1]

N += calc(A)
N += calc(B)
print(N)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())
A = [10**18] * 3
B = [10**18] * 3
dg = abs(ga - gb)
ds = abs(sa - sb)
db = abs(ba - bb)
if ga < gb:
    A[0] = ga
elif ga > gb:
    B[0] = gb
if sa < sb:
    A[1] = sa
elif sa > sb:
    B[1] = sb
if ba < bb:
    A[2] = ba
elif ba > bb:
    B[2] = bb

def calc(X):
    res = -1
    for i in range(N+1):
        if X[0] * i > N:
            break
        M = N - X[0] * i
        jj = M // X[1]
        x = 500 if x < 10000 else 100
        for j in range(max(jj - x, 0), jj+1):
            k = (M - X[1] * j) // X[2]
            res = max(res, dg * i + ds * j + db * k)
        kk = M // X[2]
        for k in range(max(kk - x, 0), kk+1):
            j = (M - X[2] * k) // X[1]
            res = max(res, dg * i + ds * j + db * k)
    return res

N += calc(A)
N += calc(B)
print(N)
Problem p03044 (python)

Fixed submission:
import sys
sys.setrecursionlimit(100000)

N = int(input())
tree = [[] for i in range(N)]
color = [-1] * N
for i in range(N-1):
    u, v, w = map(int, input().split())
    tree[u-1].append((v-1, w))
    tree[v-1].append((u-1, w))


def dfs(u):
    for v, w in tree[u]:
        if color[v] == -1:
            color[v] = color[u] ^ (w % 2)
            dfs(v)


color[0] = 0
dfs(0)
print('\n'.join(map(str, color)))

Buggy submission (verdict: Runtime Error):
N = int(input())
tree = [[] for i in range(N)]
color = [-1] * N
for i in range(N-1):
    u, v, w = map(int, input().split())
    tree[u-1].append((v-1, w))
    tree[v-1].append((u-1, w))


def dfs(u):
    for v, w in tree[u]:
        if color[v] == -1:
            color[v] = color[u] ^ (w % 2)
            dfs(v)


color[0] = 0
dfs(0)
print('\n'.join(map(str, color)))
Problem p03061 (python)

Fixed submission:
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


N = int(input())
A = list(map(int, input().split()))

gcd_from_right = [0] * N
gcd_from_right[-1] = A[-1]
for i in reversed(range(N-1)):
    gcd_from_right[i] = gcd(A[i], gcd_from_right[i+1])

ans = gcd_from_right[1]
gcd_from_left = A[0]
for i in range(1, N-1):
    ans = max(ans, gcd(gcd_from_left, gcd_from_right[i+1]))
    gcd_from_left = gcd(gcd_from_left, A[i])
ans = max(ans, gcd_from_left)
print(ans)

Buggy submission (verdict: Runtime Error):
#![allow(non_snake_case)]

fn read_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read_line()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn gcd(a: i64, b: i64) -> i64 {
    if b == 0 {
        a
    } else {
        gcd(b, a%b)
    }
}

fn main() {
    let N: usize = read_line().parse().unwrap();
    let A = read_vec();

    let mut left = vec![0; N];
    let mut right = vec![0; N];

    left[0] = A[0];
    for i in 1..N {
        left[i] = gcd(left[i-1], A[i]);
    }
    right[N-1] = A[N-1];
    for i in (0..N-1).rev() {
        right[i] = gcd(right[i+1], A[i]);
    }

    let mut max = right[1];
    for i in 1..N-1 {
        max = std::cmp::max(max, gcd(left[i-1], right[i+1]));
    }
    max = std::cmp::max(max, left[N-2]);
    println!("{}", max);
}

Buggy submission (verdict: Runtime Error):
from math import gcd

N = int(input())
A = list(map(int, input().split()))

gcd_from_right = [0] * N
gcd_from_right[-1] = A[-1]
for i in reversed(range(N-1)):
    gcd_from_right[i] = gcd(A[i], gcd_from_right[i+1])

ans = gcd_from_right[1]
gcd_from_left = A[0]
for i in range(1, N-1):
    ans = max(ans, gcd(gcd_from_left, gcd_from_right[i+1]))
    gcd_from_left = gcd(gcd_from_left, A[i])
ans = max(ans, gcd_from_left)
print(ans)
Problem p03171 (python)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

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

INF = 10**18
dp = [[INF] * N for _ in range(N)]

# def calc(i, j, t):
#     if dp[i][j] != INF:
#         return dp[i][j]
#     if t == 0:
#         if i == j:
#             dp[i][j] = a[i]
#         else:
#             dp[i][j] = max(calc(i+1, j, 1) + a[i], calc(i, j-1, 1) + a[j])
#     else:
#         if i == j:
#             dp[i][j] = -a[i]
#         else:
#             dp[i][j] = min(calc(i+1, j, 0) - a[i], calc(i, j-1, 0) - a[j])
#     return dp[i][j]

# print(calc(0, N-1, 0))

for l in range(N):
    t = (N-l) % 2
    for i in range(N-l):
        j = i + l
        if t == 1:
            if l == 0:
                dp[i][j] = a[i]
            else:
                dp[i][j] = max(dp[i+1][j] + a[i], dp[i][j-1] + a[j])
        else:
            if l == 0:
                dp[i][j] = -a[i]
            else:
                dp[i][j] = min(dp[i+1][j] - a[i], dp[i][j-1] - a[j])
print(dp[0][N-1])

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

INF = 10**18

dp0 = [[INF] * N for _ in range(N)]
dp1 = [[INF] * N for _ in range(N)]

def calc(i, j, t):
    if t == 0:
        if dp0[i][j] == INF:
            if i == j:
                dp0[i][j] = a[i]
            else:
                dp0[i][j] = max(calc(i+1, j, 1) + a[i], calc(i, j-1, 1) + a[j])
        return dp0[i][j]
    else:
        if dp1[i][j] == INF:
            if i == j:
                dp1[i][j] = -a[i]
            else:
                dp1[i][j] = min(calc(i+1, j, 0) - a[i], calc(i, j-1, 0) - a[j])
        return dp1[i][j]

print(calc(0, N-1, 0))
Problem p03177 (python)

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

def matmul(a, b, mod):
    m = len(a)
    l = len(a[0])
    n = len(b[0])
    ret = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            e = 0
            for k in range(l):
                e = (e + a[i][k] * b[k][j]) % mod
            ret[i][j] = e
    return ret

mod = 10**9+7
N, K = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
ans = [[i == j for j in range(N)] for i in range(N)]
while K > 0:
    if K & 1 == 1:
        ans = matmul(ans, a, mod)
    a = matmul(a, a, mod)
    K >>= 1
print(sum(sum(row) % mod for row in ans) % mod)

Buggy submission (verdict: Runtime Error):
import numpy as np
import sys
input = sys.stdin.readline

mod = 10**9+7
N, K = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(N)], dtype=np.int64)
ans = np.identity(N, dtype=np.int64)
while K > 0:
    if K & 1 == 1:
        ans = np.matmul(ans, a) % mod
    a = np.matmul(a, a) % mod
    K >>= 1
print(np.sum(ans) % mod)
Problem p03216 (python)

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

def main():
    N = int(input())
    S = input().rstrip()
    Q = int(input())
    k = list(map(int, input().split()))

    for l in k:
        D = 0
        M = 0
        tmp = 0
        ans = 0
        for i in range(N):
            if i >= l:
                if S[i-l] == 'D':
                    tmp -= M
                    D -= 1
                if S[i-l] == 'M':
                    M -= 1
            if S[i] == 'D':
                D += 1
            if S[i] == 'M':
                M += 1
                tmp += D
            if S[i] == 'C':
                ans += tmp
        print(ans)

main()

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    S = [input().rstrip()]
    Q = int(input())
    k = list(map(int, input().split()))

    for l in k:
        D = 0
        M = 0
        tmp = 0
        ans = 0
        for i in range(N):
            if i >= l:
                if S[i-l] == 'D':
                    tmp -= M
                    D -= 1
                if S[i-l] == 'M':
                    M -= 1
            if S[i] == 'D':
                D += 1
            if S[i] == 'M':
                M += 1
                tmp += D
            if S[i] == 'C':
                ans += tmp
        print(ans)

main()