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

Fixed submission:
from heapq import heappop, heappush


def solve(n, m, s):
    curr = n
    l = max(0, n - m)
    r = n
    ans = []
    while r > 0:
        for i, c in enumerate(s[l:r], start=l):
            if c == '0':
                dice = curr - i
                ans.append(dice)
                curr = i
                l = max(0, i - m)
                r = i
                break
        else:
            return (-1,)

    return reversed(ans)


n, m = map(int, input().split())
s = input()
print(*solve(n, m, s))

Buggy submission (verdict: Runtime Error):
class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        while i > 1:
            y = self.tree[i ^ 1]
            if y <= x:
                break
            i >>= 1
            self.tree[i] = x

    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result = min(result, self.tree[r - 1])
            if l & 1:
                result = min(result, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return result


def solve(n, m, s):
    INF = 10 ** 18
    sgt = SegTreeMin(n + 1, (INF,))
    sgt.update(0, (0, 0))
    for i in range(1, n + 1):
        if s[i] == '1':
            continue
        r = i
        l = max(0, i - m)
        prev = sgt.get_min(l, r)
        if prev[0] == INF:
            return (-1,)
        dice = i - prev[-1]
        curr = (prev[0] + 1, *prev[1:-1], dice, i)
        sgt.update(i, curr)
    return sgt.get_min(n, n + 1)[1:-1]


n, m = map(int, input().split())
s = input()
print(*solve(n, m, s))
Problem p02899 (python)

Fixed submission:
from operator import itemgetter
n = int(input())
aaa = list(map(int, input().split()))
bbb = sorted(list(enumerate(aaa, start=1)), key=itemgetter(1))
print(*map(itemgetter(0), bbb))

Buggy submission (verdict: Runtime Error):
n = int(input())
aaa = list(map(int, input().split()))
bbb = sorted(list(enumerate(aaa, start=1)), key=itemgetter(1))
print(*map(itemgetter(0), bbb))
Problem p02900 (python)

Fixed submission:
from fractions import gcd
a, b = map(int, input().split())
g = gcd(a, b)
ans = 1
for i in range(2, int(g ** 0.5) + 1):
  if g % i != 0:
    continue
  while g % i == 0:
    g //= i
  ans += 1
if g > 1:
  ans += 1
print(ans)

Buggy submission (verdict: Runtime Error):
from math import gcd
a, b = map(int, input().split())
g = gcd(a, b)
ans = 1
for i in range(2, int(g ** 0.5) + 1):
  if g % i != 0:
    continue
  while g % i == 0:
    g //= i
  ans += 1
print(ans)
Problem p02901 (python)

Fixed submission:
import sys

n, m = map(int, input().split())
INF = 10 ** 9
dp = [INF] * (1 << n)
dp[0] = 0
bits = [0] + [1 << i for i in range(n)]
get_bits = bits.__getitem__

for _ in [0] * m:
  a, b = map(int, sys.stdin.readline().split())
  s = sum(map(get_bits, map(int, sys.stdin.readline().split())))
  for t in range(1 << n):
    if (dp[t] == -1):
      continue
    dp[t | s] = min(dp[t | s], dp[t] + a)

print(dp[-1] if dp[-1] != INF else -1)

Buggy submission (verdict: Runtime Error):
import sys

n, m = map(int, input().split())
dp = [-1] * (1 << n)
dp[0] = 0
bits = [0] + [1 << i for i in range(n)]
get_bits = bits.__getitem__

for _ in [0] * m:
  a, b = map(int, sys.stdin.readline())
  s = sum(map(get_bits, map(int, sys.stdin.readline())))
  for t in range(1 << n):
    if (dp[t] == -1):
      continue
    dp[t | s] = min(dp[t | s], dp[t] + a)

print(dp[-1])
Problem p02905 (python)

Fixed submission:
import sys


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    solo_invs = [0] + [f * i % MOD for f, i in zip(factorials, invs[1:])]

    return factorials, invs, solo_invs


def decompose_inverses(solo_invs, MOD):
    # 各整数 g に対して、g の約数である各 i について dcm[i] を全て足すと 1/g になるような数列を作成
    n = len(solo_invs)
    dcm = solo_invs[:]
    for i in range(1, n):
        d = dcm[i]
        for j in range(2 * i, n, i):
            dcm[j] -= d
    for i in range(1, n):
        dcm[i] %= MOD
    return dcm


n, *aaa = map(int, sys.stdin.buffer.read().split())
MOD = 998244353
LIMIT = max(aaa)
count = [0] * (LIMIT + 1)
double = [0] * (LIMIT + 1)
for a in aaa:
    count[a] += a
    double[a] += a * a
_, _, solo_invs = prepare(LIMIT, MOD)
dcm = decompose_inverses(solo_invs, MOD)

ans = 0
inv2 = solo_invs[2]
for d in range(1, LIMIT + 1):
    ans = (ans + dcm[d] * (sum(count[d::d]) ** 2 - sum(double[d::d])) * inv2) % MOD
print(ans)

Buggy submission (verdict: Runtime Error):
import sys


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    solo_invs = [0] + [f * i % MOD for f, i in zip(factorials, invs[1:])]

    return factorials, invs, solo_invs


def decompose_inverses(solo_invs, MOD):
    # 各整数 g に対して、g の約数である各 i について dcm[i] を全て足すと 1/g になるような数列を作成
    n = len(solo_invs)
    dcm = solo_invs.copy()
    for i in range(1, n):
        d = dcm[i]
        for j in range(2 * i, n, i):
            dcm[j] -= d
    for i in range(1, n):
        dcm[i] %= MOD
    return dcm


n, *aaa = map(int, sys.stdin.buffer.read().split())
MOD = 998244353
LIMIT = max(aaa)
count = [0] * (LIMIT + 1)
double = [0] * (LIMIT + 1)
for a in aaa:
    count[a] += a
    double[a] += a * a
_, _, solo_invs = prepare(LIMIT, MOD)
dcm = decompose_inverses(solo_invs, MOD)

ans = 0
inv2 = solo_invs[2]
for d in range(1, LIMIT + 1):
    ans = (ans + dcm[d] * (sum(count[d::d]) ** 2 - sum(double[d::d])) * inv2) % MOD
print(ans)
Problem p02920 (python)

Fixed submission:
from collections import Counter
from heapq import heappop, heappush


def solve(n, sss):
    ccc = Counter(sss)
    keys = sorted(ccc.keys(), reverse=True)
    if ccc[keys[0]] != 1:
        return False

    q = [(1, keys[0])]
    for k in keys[1:]:
        nq = []
        for _ in range(ccc[k]):
            try:
                r, s = heappop(q)
            except IndexError:
                return False
            if r < n:
                nq.append((r + 1, k))
                heappush(q, (r + 1, s))
        for item in nq:
            heappush(q, item)

    return True


n = int(input())
sss = list(map(int, input().split()))
print('Yes' if solve(n, sss) else 'No')

Buggy submission (verdict: Runtime Error):
from collections import Counter
from heapq import heappush, heappop


def solve(n, sss):
    keys = [-1] + sorted(sss.keys())
    m = keys.pop()
    if sss[m] != 1:
        return False
    k = keys[-1]
    q = [(-n, -m)]
    while k != -1:
        r, s = heappop(q)
        r = -r
        s = -s
        if r == 0:
            continue
        if k >= s:
            tmp = set()
            while q:
                tmp.add((-r, -s))
                r, s = heappop(q)
                r, s = -r, -s
                if k < s:
                    for item in tmp:
                        heappush(q, item)
                    break
            else:
                return False
        heappush(q, (-(r - 1), -k))
        heappush(q, (-(r - 1), -s))
        sss[k] -= 1
        if sss[k] == 0:
            keys.pop()
            k = keys[-1]
        # print(s, r, q, keys, sss)
    return True


n = int(input())
sss = Counter(map(int, input().split()))
print('Yes' if solve(n, sss) else 'No')
Problem p02928 (python)

Fixed submission:
from collections import Counter


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
bit = Bit(2001)
single = 0
for a in reversed(aaa):
    single += bit.sum(a)
    bit.add(a + 1, 1)
ans = single * k % MOD
coef = k * (k - 1) // 2 % MOD
cnt = Counter(aaa)
before = 0
for a, c in sorted(cnt.items()):
    ans = (ans + c * before * coef) % MOD
    before += c
print(ans)

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


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
bit = Bit(n + 1)
single = 0
for a in reversed(aaa):
    single += bit.sum(a)
    bit.add(a + 1, 1)
ans = single * k % MOD
coef = k * (k - 1) // 2
cnt = Counter(aaa)
before = 0
for a, c in sorted(cnt.items()):
    ans = (ans + c * before * coef) % MOD
    before += c
print(ans)

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


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
bit = Bit(n)
single = 0
for a in reversed(aaa):
    single += bit.sum(a - 1)
    bit.add(a, 1)
ans = single * k % MOD
coef = k * (k - 1) // 2
cnt = Counter(aaa)
before = 0
for a, c in sorted(cnt.items()):
    ans = (ans + c * before * coef) % MOD
    before += c
print(ans)
Problem p02962 (python)

Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)


def rolling_hash(s, w, MOD):
    ret = []
    tmp = 0
    p = pow(26, w, MOD)
    ords = [ord(c) - 97 for c in s]
    for i, o in enumerate(ords):
        tmp = tmp * 26 + o
        if i >= w:
            tmp = (tmp - ords[i - w] * p)
        tmp %= MOD
        ret.append(tmp)
    return ret


def solve(s, t):
    MOD = 10 ** 9 + 7
    ls, lt = len(s), len(t)
    k = (lt - 1) // ls + 1
    s *= k * 2
    ls *= k
    rs, rt = rolling_hash(s, lt, MOD), rolling_hash(t, lt, MOD)
    rs = rs[ls:]
    ht = rt[-1]

    checked = [-1] * ls

    def series(i, st):
        if st <= i < st + lt:
            return float('-inf')
        if checked[i] == -1:
            checked[i] = series((i + lt) % ls, st) + 1 if rs[i] == ht else 0
        return checked[i]

    for i, hs in enumerate(rs):
        if hs != ht:
            continue
        ret = series((i + lt) % ls, i)
        if ret == float('-inf'):
            return -1
        checked[i] = ret + 1

    return max(0, max(checked))


s = input()
t = input()
print(solve(s, t))

Buggy submission (verdict: Runtime Error):
def rolling_hash(s, w, MOD):
    ret = []
    tmp = 0
    p = pow(26, w, MOD)
    ords = [ord(c) - 97 for c in s]
    for i, o in enumerate(ords):
        tmp = tmp * 26 + o
        if i >= w:
            tmp = (tmp - ords[i - w] * p)
        tmp %= MOD
        ret.append(tmp)
    return ret


def solve(s, t):
    MOD = 10 ** 9 + 7
    ls, lt = len(s), len(t)
    k = (lt - 1) // ls + 1
    s *= k * 2
    ls *= k
    rs, rt = rolling_hash(s, lt, MOD), rolling_hash(t, lt, MOD)
    rs = rs[ls:]
    ht = rt[-1]

    checked = [-1] * ls

    def series(i, st):
        if i == st:
            return float('-inf')
        if checked[i] == -1:
            checked[i] = series((i + lt) % ls, st) + 1 if rs[i] == ht else 0
        return checked[i]

    for i, hs in enumerate(rs):
        if hs != ht:
            continue
        ret = series((i + lt) % ls, i)
        if ret == float('-inf'):
            return -1
        checked[i] = ret + 1

    return max(0, max(checked))


s = input()
t = input()
print(solve(s, t))
Problem p02963 (python)

Fixed submission:
def solve(s):
    k = 10 ** 9
    if s <= k:
        return 0, 0, 1, 0, 0, s
    X = k
    while True:
        Y = (s - 1) // X + 1
        while Y <= k:
            xy = X * Y - s
            if xy == 0:
                return 0, 0, X, 0, 0, Y
            lim = min(Y, int(xy ** 0.5))
            for y in range(1, lim + 1):
                x, m = divmod(xy, y)
                if x <= X and m == 0:
                    return 0, 0, X, y, x, Y
            Y += 1
        X -= 1


s = int(input())
print(*solve(s))

Buggy submission (verdict: Runtime Error):
def solve(s):
    k = 10 ** 9
    if s <= k:
        return 0, 0, 1, 0, 0, s
    X = k
    Y = (s - 1) // X + 1
    while Y <= k:
        xy = X * Y - s
        lim = min(Y, int(xy ** 0.5))
        for y in range(1, lim + 1):
            x, m = divmod(xy, y)
            if x <= X and m == 0:
                return 0, 0, X, y, x, Y
        Y += 1


s = int(input())
print(*solve(s))

Buggy submission (verdict: Runtime Error):
def solve(s):
    if s <= 10 ** 9:
        return 0, 0, 1, 0, 0, s
    X = 10 ** 9
    Y = (s - 1) // X + 1
    xy = X * Y - s
    lim = min(Y, int(xy ** 0.5))
    for y in range(1, lim + 1):
        x, m = divmod(xy, y)
        if x <= X and m == 0:
            return 0, 0, X, y, x, Y


s = int(input())
print(*solve(s))

Buggy submission (verdict: Runtime Error):
def solve(s):
    if s <= 10 ** 9:
        return 0, 0, 0, 1, 0, s
    X = 10 ** 9
    Y = (s - 1) // X + 1
    xy = X * Y - s
    lim = min(Y, int(xy ** 0.5))
    for y in range(1, lim + 1):
        x, m = divmod(xy, y)
        if x <= X and m == 0:
            return 0, 0, X, y, x, Y


s = int(input())
print(*solve(s))
Problem p02965 (python)

Fixed submission:
from functools import lru_cache


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


def get_nhr(n, facts, invs):
    @lru_cache(maxsize=None)
    def nhr(r):
        return facts[n + r - 1] * invs[r] * invs[n - 1] % MOD

    return nhr


MOD = 998244353
n, m = list(map(int, input().split()))
facts, invs = prepare(n + 3 * m, MOD)
nhr = get_nhr(n, facts, invs)
ans = 0
for odd in range(m % 2, min(m, n) + 1, 2):
    tmp = nhr((3 * m - odd) // 2)
    if odd > 0:
        tmp -= odd * nhr((m - odd) // 2)
    if odd < n and odd <= m - 2:
        tmp -= (n - odd) * nhr((m - odd - 2) // 2)
    ans = (ans + facts[n] * invs[odd] * invs[n - odd] % MOD * tmp) % MOD
print(ans)

Buggy submission (verdict: Runtime Error):
from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 7 + 10)


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


@lru_cache(maxsize=None)
def pattern(t, k, x):
    # print('', t, k, x)
    if k * x < t:
        # print(t, k, x, 0)
        return 0
    if k * x == t or t == 0 or k == 1:
        # print(t, k, x, 1)
        return 1
    ans = pattern(t, k, x - 1)
    # print(f'  ({t} {k} {x} 0 {ans})')
    for i in range(1, t // x + 1):
        ans = (ans + pattern(t - x * i, k - i, x - 1) * facts[k] * invs[i] * invs[k - i]) % MOD
        # print(f'  ({t} {k} {x} {i} {ans})')

    # print(t, k, x, ans)
    return ans


MOD = 998244353
n, m = list(map(int, input().split()))
facts, invs = prepare(n, MOD)
print(pattern(3 * m, n, 2 * m))
Problem p02972 (python)

Fixed submission:
n = int(input())
aaa = list(map(int, input().split()))
aaa = [0] + aaa
for i in range(n // 2, 0, -1):
    b = 0
    j = i * 2
    while n >= j:
        b ^= aaa[j]
        j += i
    aaa[i] ^= b

ans = [i for i, b in enumerate(aaa) if b]
print(len(ans))
print(*ans)

Buggy submission (verdict: Runtime Error):
n = int(input())
a = [0] + list(map(int, input().split()))
for i in range(n // 2, 0, -1):
    a[i] ^= a[i * 2::i]

s = [i for i, b in enumerate(a) if b]
print(len(s))
print(*s)
Problem p03004 (python)

Fixed submission:
import sys

from math import floor


def check(t):
    maxx, minx, maxy, miny = ud_maxx, ud_minx, lr_maxy, lr_miny
    for x, y in dots['R']:
        maxx = max(maxx, x + t)
        minx = min(minx, x + t)
    for x, y in dots['L']:
        maxx = max(maxx, x - t)
        minx = min(minx, x - t)
    for x, y in dots['U']:
        maxy = max(maxy, y + t)
        miny = min(miny, y + t)
    for x, y in dots['D']:
        maxy = max(maxy, y - t)
        miny = min(miny, y - t)
    return (maxx - minx) * (maxy - miny)


n = int(input())
dots = {'R': set(), 'L': set(), 'U': set(), 'D': set()}
lr_maxy, lr_miny, ud_maxx, ud_minx = -1e9, 1e9, -1e9, 1e9
for line in sys.stdin:
    x, y, d = line.rstrip().split()
    x, y = int(x), int(y)
    dots[d].add((x, y))
    if d in 'LR':
        lr_maxy = max(lr_maxy, y)
        lr_miny = min(lr_miny, y)
    else:
        ud_maxx = max(ud_maxx, x)
        ud_minx = min(ud_minx, x)

l = 0.0
r = float(1 << 30)

while l < r - 1:
    m1 = l + floor((r - l) / 3 * 2) / 2
    m2 = l + floor((r - l) / 3 * 4) / 2
    c1 = check(m1)
    c2 = check(m2)
    # print(l, r, m1, m2, c1, c2)
    if c1 >= c2:
        l = m1
    else:
        r = m2

ans = float(1e17)
l = max(0.0, floor(l * 2 - 16) / 2)
while l <= r + 8:
    ans = min(ans, check(l))
    l += 0.5
print(ans)

Buggy submission (verdict: Runtime Error):
import sys


def check(t):
    maxx, minx, maxy, miny = -1e9, 1e9, -1e9, 1e9
    for x, y in dots['R']:
        maxx = max(maxx, x + t)
        minx = min(minx, x + t)
        maxy = max(maxy, y)
        miny = min(miny, y)
    for x, y in dots['L']:
        maxx = max(maxx, x - t)
        minx = min(minx, x - t)
        maxy = max(maxy, y)
        miny = min(miny, y)
    for x, y in dots['U']:
        maxx = max(maxx, x)
        minx = min(minx, x)
        maxy = max(maxy, y + t)
        miny = min(miny, y + t)
    for x, y in dots['D']:
        maxx = max(maxx, x)
        minx = min(minx, x)
        maxy = max(maxy, y - t)
        miny = min(miny, y - t)
    return (maxx - minx) * (maxy - miny)


n = int(input())
dots = {'R': set(), 'L': set(), 'U': set(), 'D': set()}
for line in sys.stdin():
    x, y, d = line.rstrip().split()
    x, y = int(x), int(y)
    dots[d].add((x, y))

l = 0
r = 2 * (10 ** 8)

while l < r:
    m1 = (l + r) / 2
    m2 = m1 + 0.5
    c1 = check(m1)
    c2 = check(m2)
    if c1 > c2:
        l = m1
    else:
        r = m2

ans = 10 ** 18
l = int(l * 2) / 2
while l <= r:
    ans = min(ans, check(l))
    l += 0.5
print(ans)
Problem p03014 (python)

Fixed submission:
import sys

h, w = list(map(int, input().split()))
field = [line.rstrip() for line in sys.stdin]

l = [[0] * (w + 2) for _ in [0] * (h + 2)]
r = [[0] * (w + 2) for _ in [0] * (h + 2)]
u = [[0] * (w + 2) for _ in [0] * (h + 2)]
d = [[0] * (w + 2) for _ in [0] * (h + 2)]

for i in range(1, h + 1):
    fi = field[i - 1]
    li = l[i]
    for j in range(1, w + 1):
        c = fi[j - 1]
        u[i][j] = u[i - 1][j] + 1 if c == '.' else 0
        li[j] = li[j - 1] + 1 if c == '.' else 0
for i in range(h, 0, -1):
    fi = field[i - 1]
    ri = r[i]
    for j in range(w, 0, -1):
        c = fi[j - 1]
        d[i][j] = d[i + 1][j] + 1 if c == '.' else 0
        ri[j] = ri[j + 1] + 1 if c == '.' else 0

ans = 0
for i in range(1, h + 1):
    li, ri, ui, di = l[i], r[i], u[i], d[i]
    ans = max(ans, max(li[j] + ri[j] + ui[j] + di[j] for j in range(1, w + 1)))
print(ans - 3)

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

h, w = list(map(int, input().split()))
field = [line.rstrip() for line in sys.stdin]

l = [[0] * (w + 2) for _ in [0] * (h + 2)]
r = [[0] * (w + 2) for _ in [0] * (h + 2)]
u = [[0] * (w + 2) for _ in [0] * (h + 2)]
d = [[0] * (w + 2) for _ in [0] * (h + 2)]

for i in range(1, h + 1):
    fi = field[i - 1]
    l_tmp = 0
    li = l[i]
    for j in range(1, w + 1):
        c = fi[j - 1]
        u[i][j] = u[i - 1][j] + 1 if c == '.' else 0
        li[j] = l_tmp = l_tmp + 1 if c == '.' else 0
for i in range(h, 0, -1):
    fi = field[i - 1]
    r_tmp = 0
    ri = r[i]
    for j in range(w, 0, -1):
        c = fi[j - 1]
        d[i][j] = d[i + 1][j] + 1 if c == '.' else 0
        ri[j] = r_tmp = r_tmp + 1 if c == '.' else 0

print(sum(map(np.array, [l, r, u, d])).max() - 3)

Buggy submission (verdict: Runtime Error):
import sys

import numpy as np

h, w = list(map(int, input().split()))
field = [[int(c == '.') for c in line.rstrip()] for line in sys.stdin]
field = np.array(field)


def cumsum(f):
    result = np.zeros((h, w), dtype=np.int)
    for i, row in enumerate(f):
        ri = result[i]
        tmp = 0
        for j, c in enumerate(row):
            tmp = (tmp + c) * c
            ri[j] += tmp
        tmp = 0
        for j, c in reversed(list(enumerate(row))):
            tmp = (tmp + c) * c
            ri[j] += tmp
    return result


ans = cumsum(field)
ans += cumsum(field.T).T

print(ans.max() - 3)
Problem p03032 (python)

Fixed submission:
from itertools import accumulate

n, k = list(map(int, input().split()))
vvv = list(map(int, input().split()))

dpl, dpr = [-10 ** 9] * (k + 1), [-10 ** 9] * (k + 1)
dpl[0] = dpr[0] = 0

for i in range(min(n, k)):
    i += 1
    vv = vvv[:i]
    vv.sort(reverse=True)
    sm = sum(vv)
    dpl[i] = max(dpl[i], sm)
    # print(i, vv, dpl)
    while i < k and vv:
        sm -= vv.pop()
        i += 1
        dpl[i] = max(dpl[i], sm)
    # print(i, vv, dpl)

vvv.reverse()

for i in range(min(n, k)):
    i += 1
    vv = vvv[:i]
    vv.sort(reverse=True)
    sm = sum(vv)
    dpr[i] = max(dpr[i], sm)
    # print(i, vv, dpr)
    while i < k and vv:
        sm -= vv.pop()
        i += 1
        dpr[i] = max(dpr[i], sm)
    # print(i, vv, dpr)

# print(dpl)
# print(dpr)
acl = list(accumulate(dpl, func=max))
acr = list(accumulate(dpr, func=max))
# print(acl)
# print(acr)
ans = 0
for i in range(k + 1):
    ans = max(ans, acl[i] + acr[k - i])
max_ans = sum(v for v in vvv if v > 0)
ans = min(ans, max_ans)
print(ans)

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


def make_dp(vvv, n, k):
    dp = [-(10 ** 9) * (k + 1)]
    dp[0] = 0

    for i in range(min(n, k)):
        i += 1
        vv = vvv[:i]
        vv.sort(reverse=True)
        sm = sum(vv)
        dp[i] = max(dp[i], sm)
        while i < k and vv and vv[-1] < 0:
            sm -= vv.pop()
            i += 1
            dp[i] = max(dp[i], sm)

    return list(accumulate(dp, func=max))


n, k = list(map(int, input().split()))
vvv = list(map(int, input().split()))

acl = make_dp(vvv, n, k)
acr = make_dp(reversed(vvv), n, k)

ans = max(acl[i] + acr[k - i] for i in range(k + 1))
ans = min(ans, sum(v for v in vvv if v > 0))
print(ans)
Problem p03037 (python)

Fixed submission:
import sys

n, m = list(map(int, input().split()))
l, r = 1, n
for line in sys.stdin:
    a, b = list(map(int, line.split()))
    l = max(a, l)
    r = min(b, r)
print(max(0, r - l + 1))

Buggy submission (verdict: Runtime Error):
import sys

n, m = list(map(int, input().split()))
l, r = 1, n
for line in sys.stdin:
    a, b = list(map(int, input().split()))
    l = max(a, l)
    r = min(b, r)
print(max(0, r - l + 1))