Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):

from collections import defaultdict

def submit():
    s = [int(c) for c in input()]
    modp = 2019

    curr = 0
    modp_count = defaultdict(int)
    modp_count[0] = 1
    ans = 0
    base = 1
    for c in reversed(s):
        curr += base * c
        curr_mod = curr % modp
        ans += modp_count[curr_mod]
        modp_count[curr_mod] += 1
        base *= 10
    
    print(ans)
    

submit()
    

Fixed submission:

from collections import defaultdict

def submit():
    s = [int(c) for c in input()]
    modp = 2019

    curr = 0
    modp_count = defaultdict(int)
    modp_count[0] = 1
    ans = 0
    base = 1
    for c in reversed(s):
        curr += base * c
        curr_mod = curr % modp
        ans += modp_count[curr_mod]
        modp_count[curr_mod] += 1
        base *= 10
        base %= modp
    
    print(ans)
    

submit()
Buggy python submission (verdict: Time Limit Exceeded):


def submit():
    n = int(input())
    s = input()

    r_cnt = [0 for _ in range(n)]
    g_cnt = [0 for _ in range(n)]
    b_cnt = [0 for _ in range(n)]

    for i in reversed(range(n)):
        if s[i] == 'R':
            r_cnt[i] = 1
        if s[i] == 'G':
            g_cnt[i] = 1
        if s[i] == 'B':
            b_cnt[i] = 1

    for i in reversed(range(1, n)):
        r_cnt[i - 1] += r_cnt[i]
        g_cnt[i - 1] += g_cnt[i]
        b_cnt[i - 1] += b_cnt[i]


    ans = 0
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            if s[i] == s[j]:
                continue
            dist = j - i
            if {s[i], s[j]} == {'R', 'G'}:
                ans += b_cnt[j + 1]
                if j + dist < n and s[j + dist] == 'B':
                    ans -= 1
            elif {s[i], s[j]} == {'R', 'B'}:
                ans += g_cnt[j + 1]
                if j + dist < n and s[j + dist] == 'G':
                    ans -= 1
            else:
                ans += r_cnt[j + 1]
                if j + dist < n and s[j + dist] == 'R':
                    ans -= 1
    print(ans)


submit()    


Fixed submission:


def submit():
    n = int(input())
    s = input()

    r_cnt = [0 for _ in range(n)]
    g_cnt = [0 for _ in range(n)]
    b_cnt = [0 for _ in range(n)]

    for i in reversed(range(n)):
        if s[i] == 'R':
            r_cnt[i] = 1
        if s[i] == 'G':
            g_cnt[i] = 1
        if s[i] == 'B':
            b_cnt[i] = 1

    for i in reversed(range(1, n)):
        r_cnt[i - 1] += r_cnt[i]
        g_cnt[i - 1] += g_cnt[i]
        b_cnt[i - 1] += b_cnt[i]


    ans = 0
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            if s[i] == s[j]:
                continue
            dist = j - i
            if {s[i], s[j]} == {'R', 'G'}:
                ans += b_cnt[j + 1]
                if j + dist < n and s[j + dist] == 'B':
                    ans -= 1
            elif {s[i], s[j]} == {'R', 'B'}:
                ans += g_cnt[j + 1]
                if j + dist < n and s[j + dist] == 'G':
                    ans -= 1
            else:
                ans += r_cnt[j + 1]
                if j + dist < n and s[j + dist] == 'R':
                    ans -= 1
    print(ans)


submit()
Buggy python submission (verdict: Time Limit Exceeded):


def read_input():
    h, n = map(int, input().split())
    magic = {}
    for i in range(n):
        a, b = map(int, input().split())
        magic[i] = (a, b)

    return h, n, magic


def submit():
    h, n, magic = read_input()

    dp = [float('inf') for _ in range(h + 1)]
    dp[h] = 0

    for i in reversed(range(1, h + 1)):
        for a, b in magic.values():
            # 更新する
            # max(0, i - a)のHPにより少ない魔力消費量で行き着ければ更新する
            rest = max(0, i - a)
            if dp[rest] > dp[i] + b:
                dp[rest] = dp[i] + b

    print(dp[0])


submit()

Fixed submission:


def read_input():
    h, n = map(int, input().split())
    magic = {}
    for i in range(n):
        a, b = map(int, input().split())
        magic[i] = (a, b)

    return h, n, magic


def submit():
    h, n, magic = read_input()

    dp = [float('inf') for _ in range(h + 1)]
    dp[h] = 0

    for i in reversed(range(1, h + 1)):
        for a, b in magic.values():
            # 更新する
            # max(0, i - a)のHPにより少ない魔力消費量で行き着ければ更新する
            rest = max(0, i - a)
            if dp[rest] > dp[i] + b:
                dp[rest] = dp[i] + b

    print(dp[0])


submit()
Buggy python submission (verdict: Runtime Error):

import math


def submit():
    a, b, x = map(int, input().split())

    if x >= a*a*b/2:
        c = (2*x - a*a*b)/(a*a)
        beta = math.degrees(math.atan(a/(b-c)))
    else:
        d = 2*x/(a*b*b)
        beta = math.degrees(math.atan(d))
    
    print(90 - beta)
    

if __name__ == "__main__":
    submit()

Fixed submission:

import math


def submit():
    a, b, x = map(int, input().split())

    if x >= a*a*b/2:
        c = (2*x - a*a*b)/(a*a)
        if b == c:
            beta = 90
        else:
            beta = math.degrees(math.atan(a/(b-c)))
    else:
        d = 2*x/(a*b*b)
        beta = math.degrees(math.atan(d))
    
    print(90 - beta)
    

if __name__ == "__main__":
    submit()
Buggy python submission (verdict: Time Limit Exceeded):

import bisect


def submit():
    n = int(input())
    llist = list(map(int, input().split()))

    llist.sort()
    ans = 0
    for a in range(n):
        for b in range(a + 1, n):
            c_min = llist[b] - llist[a]
            c_max = llist[a] + llist[b]
            cs = bisect.bisect_right(llist, c_min, lo=b + 1)
            ce = bisect.bisect_left(llist, c_max, lo=b + 1)
            ans += ce - cs

    print(ans)


if __name__ == "__main__":
    submit()

Fixed submission:
import bisect


def submit():
    n = int(input())
    llist = list(map(int, input().split()))

    llist.sort()
    ans = 0
    for a in range(n):
        for b in range(a + 1, n):
            c_min = llist[b] - llist[a]
            c_max = llist[a] + llist[b]
            cs = bisect.bisect_right(llist, c_min, lo=b + 1)
            ce = bisect.bisect_left(llist, c_max, lo=b + 1)
            ans += ce - cs

    print(ans)


if __name__ == "__main__":
    submit()
Buggy python submission (verdict: Time Limit Exceeded):


def submit():
    s = input()
    t = input()

    next_char = {}
    char_list = {}

    for i in reversed(range(len(s))):
        c = s[i]
        if c not in next_char.keys():
            next_char[c] = i
            char_list[(c, i)] = -1
        else:
            char_list[(c, i)] = next_char[c]
            next_char[c] = i

    
    init_next_char = next_char.copy()
    loop = 0
    curr = 0
    for c in t:
        # 実現不可能
        if c not in next_char.keys():
            print(-1)
            return

        while 0 <= next_char[c] < curr:
            next_char[c] = char_list[(c, next_char[c])]
        
        if next_char[c] < 0:
            loop += 1
            curr = 0
            next_char = init_next_char.copy()
        
        curr = next_char[c]
        next_char[c] = char_list[(c, next_char[c])]
    print(loop * len(s) + curr + 1)
        

submit()

Fixed submission:


def submit():
    s = input()
    t = input()
    char_set = set(s)
    next_char = {c: -1 for c in char_set}
    char_list = {(c, len(s)): -1 for c in char_set}

    for i in reversed(range(len(s))):
        for c in char_set:
            if c == s[i]:
                char_list[(c, i)] = i
            else:
                char_list[(c, i)] = char_list[(c, i + 1)]
            
    loop = 0
    curr = 0
    for c in t:
        # 実現不可能
        if c not in char_set:
            print(-1)
            return
        if char_list[(c, curr)] < 0:
            loop += 1
            curr = 0
        curr = char_list[(c, curr)] + 1
    print(loop * len(s) + curr)
        

submit()
Buggy python submission (verdict: Runtime Error):


def submit():
    n = int(input())
    alist = list(map(int, input().split()))
    blist = list(map(int, input().split()))


    # 順番にグリーディ
    a = alist.copy()
    b = blist.copy()
    score_a = 0
    for i in range(0, n):
        if a[i] < b[i]:
            score_a += a[i]
            b[i] -= a[i]
            a[i] = 0
        else:
            score_a += b[i]
            a[i] -= b[i]
            b[i] = 0

        if a[i + 1] < b[i]:
            score_a += a[i + 1]
            b[i] -= a[i + 1]
            a[i + 1] = 0
        else:
            score_a += b[i]
            a[i + 1] -= b[i]
            b[i] = 0

    # 逆順にグリーディ
    a = alist.copy()
    a.reverse()
    b = alist.copy()
    b.reverse()
    score_b = 0
    for i in range(0, n):
        if a[i] < b[i]:
            score_b += a[i]
            b[i] -= a[i]
            a[i] = 0
        else:
            score_b += b[i]
            a[i] -= b[i]
            b[i] = 0

        if a[i + 1] < b[i]:
            score_b += a[i + 1]
            b[i] -= a[i + 1]
            a[i + 1] = 0
        else:
            score_b += b[i]
            a[i + 1] -= b[i]
            b[i] = 0

    print(max(score_a, score_b))
    

if __name__ == '__main__':
    submit()


Fixed submission:


def submit():
    n = int(input())
    alist = list(map(int, input().split()))
    blist = list(map(int, input().split()))


    # 順番にグリーディ
    a = alist.copy()
    b = blist.copy()
    score_a = 0
    for i in range(0, n):
        if a[i] < b[i]:
            score_a += a[i]
            b[i] -= a[i]
            a[i] = 0
        else:
            score_a += b[i]
            a[i] -= b[i]
            b[i] = 0

        if a[i + 1] < b[i]:
            score_a += a[i + 1]
            b[i] -= a[i + 1]
            a[i + 1] = 0
        else:
            score_a += b[i]
            a[i + 1] -= b[i]
            b[i] = 0


    print(score_a)


if __name__ == '__main__':
    submit()
Buggy python submission (verdict: Time Limit Exceeded):


# 10のp乗の桁のmod 13
def coefficient(p):
    a = p % 6
    if a == 0:
        return 1
    if a == 1:
        return 10
    if a == 2:
        return 9
    if a == 3:
        return 12
    if a == 4:
        return 3
    if a == 5:
        return 4


def submit():
    s = input()
    clist = [c for c in s]
    n = len(clist)
    ansmod = 10 ** 9 + 7

    # dp[x][y] : 上位x桁まで見たときに、y mod 13になるパターン数
    dp = [
        [0 for _ in range(13)] for _ in range(n + 1)
    ]

    dp[0][0] = 1

    for i, c in enumerate(clist):
        if c == '?':
            for x in range(10):
                for y in range(13):
                    dig_mod = y
                    dig_mod += coefficient(n - i - 1) * x
                    dig_mod %= 13
                    dp[i + 1][dig_mod] += dp[i][y]
                    dp[i + 1][dig_mod] %= ansmod
        else:
            x = int(c)
            for y in range(13):
                dig_mod = y
                dig_mod += coefficient(n - i - 1) * x
                dig_mod %= 13
                dp[i + 1][dig_mod] += dp[i][y]
                dp[i + 1][dig_mod] %= ansmod

    print(dp[n][5] % ansmod)


if __name__ == '__main__':
    submit()

Fixed submission:


# 10のp乗の桁のmod 13
def coefficient(p):
    a = p % 6
    if a == 0:
        return 1
    if a == 1:
        return 10
    if a == 2:
        return 9
    if a == 3:
        return 12
    if a == 4:
        return 3
    if a == 5:
        return 4


def submit():
    s = input()
    clist = [c for c in s]
    n = len(clist)
    ansmod = 10 ** 9 + 7

    # dp[x][y] : 上位x桁まで見たときに、y mod 13になるパターン数
    dp = [
        [0 for _ in range(13)] for _ in range(n + 1)
    ]

    dp[0][0] = 1

    for i, c in enumerate(clist):
        if c == '?':
            for x in range(10):
                for y in range(13):
                    dig_mod = y
                    dig_mod += coefficient(n - i - 1) * x
                    dig_mod %= 13
                    dp[i + 1][dig_mod] += dp[i][y]
                    dp[i + 1][dig_mod] %= ansmod
        else:
            x = int(c)
            for y in range(13):
                dig_mod = y
                dig_mod += coefficient(n - i - 1) * x
                dig_mod %= 13
                dp[i + 1][dig_mod] += dp[i][y]
                dp[i + 1][dig_mod] %= ansmod

    print(dp[n][5] % ansmod)


if __name__ == '__main__':
    submit()
Buggy python submission (verdict: Runtime Error):


def read_input():
    n, m = map(int, input().split())

    slist = []
    for i in range(m):
        temp = list(map(int, input().split()))
        k = temp[0]
        s = temp[1:]
        slist.append((k, s))

    p = list(map(int, input().split()))

    return n, m, slist, p


def switch_gen(n):
    curr = 0

    while True:
        bincurr = bin(curr)[2:]

        if len(bincurr) > n:
            return None
        bincurr = [int(c) for c in bincurr]
        t = [0] * (n - len(bincurr))
        t.extend(bincurr)
        yield t

        curr += 1


def check_condition(switch, slist, plist):
    for s, p in zip(slist, plist):
        count = 0
        for i in s[1]:
            if switch[i - 1] == 1:
                count += 1

        if count % 2 != p:
            return False

    return True


def submit():
    n, m, slist, p = read_input()

    count = 0
    for switch in switch_gen(n):
        if check_condition(switch, slist, p):
            count += 1

    print(count)




if __name__ == '__main__':
    submit()


Fixed submission:


def read_input():
    n, m = map(int, input().split())

    slist = []
    for i in range(m):
        temp = list(map(int, input().split()))
        k = temp[0]
        s = temp[1:]
        slist.append((k, s))

    p = list(map(int, input().split()))

    return n, m, slist, p


def switch_gen(n):
    curr = 0

    while True:
        bincurr = bin(curr)[2:]

        if len(bincurr) > n:
            return None
        bincurr = [int(c) for c in bincurr]
        t = [0] * (n - len(bincurr))
        t.extend(bincurr)
        yield t

        curr += 1


def check_condition(switch, slist, plist):
    for s, p in zip(slist, plist):
        count = 0
        for i in s[1]:
            if switch[i - 1] == 1:
                count += 1

        if count % 2 != p:
            return False

    return True


def submit():
    n, m, slist, p = read_input()

    count = 0
    for switch in switch_gen(n):
        if check_condition(switch, slist, p):
            count += 1

    print(count)




if __name__ == '__main__':
    submit()
Buggy python submission (verdict: Runtime Error):
from collections import deque

def read_input():
    n, k = map(int, input().split())
    vlist = list(map(int, input().split()))
    vq = deque()

    for v in vlist:
        vq.append(v)

    return n, k, vq


def submit():
    n, k, vq = read_input()

    maxvalue = 0
    for kk in range(1, k):
        # 左からi回宝石を取得する
        # 右からkk-i回宝石を取得する
        for i in range(kk + 1):
            getv = []
            minusv = []
            vq_temp = vq.copy()
            for j in range(i):
                if len(vq_temp) > 0:
                    vl = vq_temp.popleft()
                    if vl < 0:
                        minusv.append(vl)
                    else:
                        getv.append(vl)
                else:
                    break

            for j in range(kk - i):
                if len(vq_temp) > 0:
                    vr = vq_temp.pop()
                    if vr < 0:
                        minusv.append(vr)
                    else:
                        getv.append(vr)
                else:
                    break


            # k - kk回はminusを削除できる
            minusv.sort()
            for m in range(k - kk):
                if minusv:
                    minusv.remove(minusv[0])
                else:
                    break

            currvalue = sum(getv) + sum(minusv)

            if currvalue > maxvalue:
                maxvalue = currvalue

    print(maxvalue)







if __name__ == '__main__':
    submit()


Fixed submission:
from collections import deque

def read_input():
    n, k = map(int, input().split())
    vlist = list(map(int, input().split()))

    return n, k, vlist


def submit():
    n, k, vlist = read_input()

    maxvalue = 0
    for kk in range(1, k + 1):
        # 左からi回宝石を取得する
        # 右からkk-i回宝石を取得する
        for i in range(kk + 1):
            getv = []
            minusv = []
            vq_temp = deque()

            for v in vlist:
                vq_temp.append(v)

            for j in range(i):
                if len(vq_temp) > 0:
                    vl = vq_temp.popleft()
                    if vl < 0:
                        minusv.append(vl)
                    else:
                        getv.append(vl)
                else:
                    break

            for j in range(kk - i):
                if len(vq_temp) > 0:
                    vr = vq_temp.pop()
                    if vr < 0:
                        minusv.append(vr)
                    else:
                        getv.append(vr)
                else:
                    break


            # k - kk回はminusを削除できる
            minusv.sort()
            for m in range(k - kk):
                if minusv:
                    minusv.remove(minusv[0])
                else:
                    break

            currvalue = sum(getv) + sum(minusv)

            if currvalue > maxvalue:
                maxvalue = currvalue

    print(maxvalue)

if __name__ == '__main__':
    submit()
Buggy python submission (verdict: Time Limit Exceeded):


def read_input():
    n, m = map(int, input().split())
    alist = list(map(int, input().split()))

    clist = []
    for i in range(m):
        b, c = map(int, input().split())

        clist.extend([c]*b)

    return alist, clist

def submit():
    alist, clist = read_input()

    alist.sort(reverse=False)
    clist.sort(reverse=True)

    j = 0
    result = 0
    for a in alist:
        if j >= len(clist):
            result += a
        elif a >= clist[j]:
            result += a
        else:
            result += clist[j]
            j += 1

    print(result)



if __name__ == '__main__':
    submit()


Fixed submission:


def read_input():
    n, m = map(int, input().split())
    alist = list(map(int, input().split()))

    clist = []
    for i in range(m):
        b, c = map(int, input().split())
        clist.append([c, b])

    return alist, clist

def submit():
    alist, clist = read_input()

    alist.sort(reverse=False)
    clist.sort(key=lambda x: x[0], reverse=True)

    j = 0
    result = 0
    for a in alist:
        if j >= len(clist):
            result += a
        elif a >= clist[j][0]:
            result += a
        else:
            if clist[j][1] > 0:
                result += clist[j][0]
                clist[j][1] -= 1
                if clist[j][1] == 0:
                    j += 1

    print(result)



if __name__ == '__main__':
    submit()
Buggy python submission (verdict: Runtime Error):
import math

def read_input():
    n, k = map(int, input().split())
    return n, k


# x*2^d >= k となる最小のkを求める
def calc_d(x, k):
    return int(math.ceil(math.log2(k/x)))


def submit():
    n, k = read_input()

    result = 0
    for i in range(1, n + 1):
        if i < k:
            result += math.pow((1/2), calc_d(i, k))
        else:
            result += 1.0

    print(result/n)


if __name__ == '__main__':
    submit()


Fixed submission:
import math

def read_input():
    n, k = map(int, input().split())
    return n, k


# x*2^d >= k となる最小のkを求める
def calc_d(x, k):
    return int(math.ceil(math.log2(k/x)))


def submit():
    n, k = read_input()

    result = 0
    for i in range(1, n + 1):
        if i < k:
            result += math.pow((1/2), calc_d(i, k))
        else:
            result += 1.0

    print(result/n)


if __name__ == '__main__':
    submit()
Buggy python submission (verdict: Time Limit Exceeded):

def read_input():
    n, k = map(int, input().split())
    s = list(map(int, list(str(input()))))

    return n, k, s


# 0, 1, ....を(0, n1), (1, n2)みたいな形にする
def convert_01(s):
    result = []

    result.append([s[0], 1])
    for ss in s[1:]:
        if result[-1][0] == ss:
            result[-1][1] += 1
        else:
            result.append([ss, 1])

    return result


# index以降の要素、かつ0の数がKを下回るサブリストにある要素をカウントする
def get_elements_in_subliist(r, index, k):
    count = 0

    zeros = 0
    for i in range(index, len(r)):
        if r[i][0] == 0:
            zeros += 1

        if r[i][0] == 0 and zeros > k:
            return count

        count += r[i][1]

    return count




if __name__ == '__main__':
    n, k, s = read_input()

    r = convert_01(s)

    max_count = 0
    for i in range(n):
        t = get_elements_in_subliist(r, i, k)
        if t > max_count:
            max_count = t

    print(max_count)

Fixed submission:

import queue

def read_input():
    n, k = map(int, input().split())
    s = list(map(int, list(str(input()))))

    return n, k, s


# 0, 1, ....を(0, n1), (1, n2)みたいな形にする
def convert_01(s):
    result = []

    result.append([s[0], 1])
    for ss in s[1:]:
        if result[-1][0] == ss:
            result[-1][1] += 1
        else:
            result.append([ss, 1])

    return result


# index以降の要素、かつ0の数がKを下回るサブリストにある要素をカウントする
def get_count(r,k):
    count = 0
    max_count = 0
    zeros = 0

    q = queue.Queue()

    for e in r:
        if e[0] == 0 and zeros >= k:
        # すでにk回0を操作した
            while True:
                t = q.get()
                count -= t[1]

                if t[0] == 0:
                    zeros -= 1
                    break

        q.put(e)
        count += e[1]

        if e[0] == 0:
            zeros += 1

        if max_count < count:
            max_count = count

    return max_count






if __name__ == '__main__':
    n, k, s = read_input()
    r = convert_01(s)

    print(get_count(r, k))
Buggy python submission (verdict: Runtime Error):

def read_input1():
    n, k = map(int, input().split())

    data_tuples = []
    for i in range(n):
        data_tuples.append(tuple(map(int, input().split())))

    return n, k, data_tuples


def count_neta(sushi_set):
    neta = {s[0] for s in sushi_set}
    return len(neta)


def sum_oishisa(sushi_set):
    oishisa = [s[1] for s in sushi_set]
    return sum(oishisa)


def check_value(sushi_set):
    neta_count = count_neta(sushi_set)
    oishisa = sum_oishisa(sushi_set)

    return oishisa + (neta_count * neta_count)


# ネタ数を減らさず、かつもっともおいしさの減少が少ないすしを探す
def check_changable_sushi(sushi_set):
    neta_count = count_neta(sushi_set)

    target = None
    for s in sushi_set:
        temp_sushi_set = sushi_set.remove(s)
        temp_neta_count = count_neta(temp_sushi_set)

        if neta_count == temp_neta_count:
            if target is None or target[1] > s[1]:
                target = s

        temp_sushi_set.append(s)
    return target


def find_other_sushi(all_sushi_set, sushi_set):
    neta_eaten = [s[0] for s in sushi_set]
    candidate_sushi = [sushi for sushi in all_sushi_set if sushi[0] not in neta_eaten]

    if candidate_sushi:
        target = max(candidate_sushi, key=lambda x: x[1])
    else:
        target = None

    return target


def next_neta_variation(all_sushi_set, sushi_set):
    drop_target = check_changable_sushi(sushi_set)
    if drop_target:
        insert_target = find_other_sushi(all_sushi_set, sushi_set)

        if insert_target:
            new_set = sushi_set.copy()
            new_set.remove(drop_target)
            new_set.append(insert_target)
            return new_set
    return None


if __name__ == '__main__':
    n, k, sushis = read_input1()
    neta_candidate = {}

    sushis.sort(key=lambda x: x[1], reverse=True)

    init_sushi_set = sushis[:k].copy()
    neta_count = count_neta(init_sushi_set)
    neta_candidate[neta_count] = init_sushi_set

    curr_sushi_set = init_sushi_set
    while True:
        next_sushi_set = next_neta_variation(sushis, curr_sushi_set)
        if not next_sushi_set:
            break

        curr_sushi_set = next_sushi_set
        neta_count = count_neta(curr_sushi_set)
        neta_candidate[neta_count] = curr_sushi_set

    max_score = -1
    for sushis in neta_candidate.values():
        score = check_value(sushis)
        if max_score < score:
            max_score = score

    print(max_score)


Fixed submission:
ab, bc, ca = input().split()
print(int((int(ab)*int(bc))/2))