Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import math
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    for i in range(q):
        n, x, m = map(int, input().split())
        last = x
        eq = 0
        for j in range(k):
            num = math.ceil((n-1-j)/k)
            last += (d[j] % m)*num
            if d[j] % m == 0:
                eq += num
        ans = (n-1) - (last//m - x//m) - eq
        print(ans)


main()


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


def ceil(a, b):
    return (a+b-1)//b


def main():
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    for i in range(q):
        n, x, m = map(int, input().split())
        last = x
        eq = 0
        for j in range(k):
            num = ceil((n-1-j), k)
            last += (d[j] % m)*num
            if d[j] % m == 0:
                eq += num
        ans = (n-1) - (last//m - x//m) - eq
        print(ans)


main()
Buggy python submission (verdict: Runtime Error):
def main():
    s = input()
    s = list(reversed(s))
    s.append('0')
    dp = [[10**10 for _ in range(2)] for _ in range(10**5)]
    dp[0][0] = 0
    for i in range(len(s)):
        for j in range(2):
            x = int(s[i])
            x += j
            for a in range(10):
                ni = i+1
                nj = 0
                b = a-x
                if b < 0:
                    nj = 1
                    b += 10
                dp[ni][nj] = min(dp[ni][nj], dp[i][j]+a+b)
    print(dp[len(s)][0])


main()


Fixed submission:
def main():
    s = input()
    s = list(reversed(s))
    s.append('0')
    dp = [[10**10 for _ in range(2)] for _ in range(len(s)+1)]
    dp[0][0] = 0
    for i in range(len(s)):
        for j in range(2):
            x = int(s[i])
            x += j
            for a in range(10):
                ni = i+1
                nj = 0
                b = a-x
                if b < 0:
                    nj = 1
                    b += 10
                dp[ni][nj] = min(dp[ni][nj], dp[i][j]+a+b)
    print(dp[len(s)][0])


main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))

    m = 0
    a = 0
    for i in range(n-k+1):
        wa = 0
        for j in range(k):
            wa += p[i+j]
        if m < wa:
            a = i
            m = wa

    ans = 0
    for i in range(a, a+k):
        x = p[i]
        ans += (1/2*x*(x+1))/x

    print(ans)


main()


Fixed submission:
def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))

    wa = 0
    for i in range(k):
        wa += p[i]

    m = 0
    a = 0
    for i in range(1, n-k+1):
        wa -= p[i-1]
        wa += p[i+k-1]
        if m < wa:
            a = i
            m = wa

    ans = 0
    for i in range(a, a+k):
        x = p[i]
        ans += (1/2*x*(x+1))/x

    print(ans)


main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))

    kitai = [0]*1001
    for i in range(1, 1001):
        kitai[i] = (1/2*i*(i+1))/i

    ans = 0
    for i in range(n-k+1):
        wa = 0
        for j in range(k):
            wa += kitai[p[i+j]]
        ans = max(ans, wa)

    print(ans)


main()


Fixed submission:
def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))

    wa = 0
    for i in range(k):
        wa += p[i]

    m = 0
    a = 0
    for i in range(1, n-k+1):
        wa -= p[i-1]
        wa += p[i+k-1]
        if m < wa:
            a = i
            m = wa

    ans = 0
    for i in range(a, a+k):
        x = p[i]
        ans += (1/2*x*(x+1))/x

    print(ans)


main()
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9+7


def make_combination_table(n):
    fact = [1]
    for i in range(1, n+1):
        fact.append(fact[i-1] * i % MOD)

    ifact = [0] * (n+1)
    ifact[n] = pow(fact[n], MOD-2, MOD)
    for i in range(n, 0, -1):
        ifact[i-1] = ifact[i] * i % MOD
    return (fact, ifact)


def mod_combination(n, r, table):
    if r > n:
        return 0
    return table[0][n] * table[1][n - r] * table[1][r] % MOD


def sum_rect(r, c, table):
    return (mod_combination(r+c+2, r+1, table)-1) % MOD


def main():
    r1, c1, r2, c2 = map(int, input().split())
    table = make_combination_table((r2+1)*(c2+1))
    r1 -= 1
    c1 -= 1

    ans = sum_rect(r2, c2, table)
    ans -= sum_rect(r2, c1, table)
    ans -= sum_rect(r1, c2, table)
    ans += sum_rect(r1, c1, table)
    print(ans)


main()


Fixed submission:
MOD = 10**9+7


def make_combination_table(n):
    fact = [1]
    for i in range(1, n+1):
        fact.append(fact[i-1] * i % MOD)

    ifact = [0] * (n+1)
    ifact[n] = pow(fact[n], MOD-2, MOD)
    for i in range(n, 0, -1):
        ifact[i-1] = ifact[i] * i % MOD
    return (fact, ifact)


def mod_combination(n, r, table):
    if r > n:
        return 0
    return table[0][n] * table[1][n - r] * table[1][r] % MOD


def sum_rect(r, c, table):
    return (mod_combination(r+c+2, r+1, table)-1) % MOD


def main():
    r1, c1, r2, c2 = map(int, input().split())
    table = make_combination_table((r2+c2+2))
    r1 -= 1
    c1 -= 1

    ans = sum_rect(r2, c2, table)
    ans %= MOD
    ans -= sum_rect(r2, c1, table)
    ans %= MOD
    ans -= sum_rect(r1, c2, table)
    ans %= MOD
    ans += sum_rect(r1, c1, table)
    ans %= MOD
    print(ans)


main()
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
p = list(map(int, input().split()))

ans = 0
for i in range(n):
    is_valid = True
    for j in range(i+1):
        if p[i] > p[j]:
            is_valid = False
            break
    if is_valid:
        ans += 1
print(ans)


Fixed submission:
n = int(input())
p = list(map(int, input().split()))

ans = 0
min_value = p[0]
for i in range(n):
    if p[i] <= min_value:
        ans += 1
    min_value = min(p[i], min_value)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import functools
import fractions
MOD = 10**9+7


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(numbers):
    return functools.reduce(lcm_base, numbers, 1)


def main():
    n = int(input())
    x = list(map(int, input().split()))

    l = lcm(x)
    ans = 0
    for i in range(n):
        ans += l // x[i]
        ans %= MOD

    print(ans)


main()


Fixed submission:
import functools
import fractions
MOD = 10**9+7


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(numbers):
    return functools.reduce(lcm_base, numbers, 1)


def main():
    n = int(input())
    x = list(map(int, input().split()))

    l = lcm(x)
    ans = 0
    for i in range(n):
        ans += l // x[i]

    print(ans % MOD)


main()
Buggy python submission (verdict: Time Limit Exceeded):
def search_delete(data):
    del_target = -1
    max_count = 1
    for i in range(len(data)):
        count = 0
        for j in range(i+1, len(data)):
            if data[i][1] > data[j][0]:
                count += 1
            else:
                break
        if count >= max_count:
            del_target = i
            max_count = count
    if del_target != -1:
        data.pop(del_target)
        return True
    return False


def main():
    n = int(input())
    data = []
    for i in range(n):
        x, l = map(int, input().split())
        data.append([x-l, x+l])
    data.sort(key=lambda x: x[0])

    remove = []
    for i in range(len(data)-1):
        if data[i][1] < data[i+1][0]:
            remove.append(data[i])

    for x in remove[:]:
        data.remove(x)

    flg = True
    while flg:
        flg = search_delete(data)

    print(len(remove)+len(data))


main()


Fixed submission:
def main():
    n = int(input())
    data = []
    for i in range(n):
        x, l = map(int, input().split())
        data.append([x-l, x+l])
    data.sort(key=lambda x: x[1])

    ans = 1
    min_value = data[0][1]
    for i in range(1, n):
        if min_value <= data[i][0]:
            ans += 1
            min_value = data[i][1]

    print(ans)


main()
Buggy python submission (verdict: Time Limit Exceeded):
import collections


def search(data, w, h, start, end):
    maps = [[0] * w for i in range(h)]
    move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    que = collections.deque([(start[1], start[0])])
    maps[start[1]][start[0]] = 0
    while que:
        y, x = que.popleft()
        num = maps[y][x]
        for m in move:
            if 0 <= y+m[0] < h and 0 <= x+m[1] < w:
                if maps[y+m[0]][x+m[1]] != 0:
                    continue
                if data[y+m[0]][x+m[1]] == '#':
                    continue
                elif data[y+m[0]][x+m[1]] == '.':
                    maps[y+m[0]][x+m[1]] = num+1
                    que.append((y+m[0], x+m[1]))
    return maps[end[1]][end[0]]


def main():
    h, w = map(int, input().split())
    data = []
    for i in range(h):
        tmp = input()
        data.append([j for j in tmp])

    ans = 0
    for i in range(h*w-1):
        for j in range(i+1, h*w):
            if data[i//w][i % w] == '.' and data[j//w][j % w] == '.':
                ans = max(search(data, w, h, (i % w, i//w), (j % w, j//w)), ans)
    print(ans)


main()


Fixed submission:
import collections


def search(data, w, h, start):
    maps = [[-1] * w for i in range(h)]
    move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    que = collections.deque([(start[1], start[0])])
    maps[start[1]][start[0]] = 0
    result = 0
    while que:
        y, x = que.popleft()
        num = maps[y][x]
        for m in move:
            if 0 <= y+m[0] < h and 0 <= x+m[1] < w:
                if maps[y+m[0]][x+m[1]] != -1:
                    continue
                if data[y+m[0]][x+m[1]] == '#':
                    continue
                elif data[y+m[0]][x+m[1]] == '.':
                    maps[y+m[0]][x+m[1]] = num+1
                    result = max(result, maps[y+m[0]][x+m[1]])
                    que.append((y+m[0], x+m[1]))
    return result


def main():
    h, w = map(int, input().split())
    data = []
    for i in range(h):
        tmp = input()
        data.append([j for j in tmp])

    ans = 0
    for i in range(h*w-1):
        if data[i//w][i % w] == '.':
            ans = max(search(data, w, h, (i % w, i//w)), ans)
    print(ans)


main()
Buggy python submission (verdict: Time Limit Exceeded):
import math

MOD = 10**9+7


def make_combination_table(n):
    result = []
    for i in range(n):
        result.append(math.factorial(i))
    return result


def mod_combination(n, r, table):
    if r > n:
        return 0
    return table[n] // (table[n - r] * table[r]) % MOD


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    c_table = make_combination_table(n)
    ans = 0
    a.sort()
    for i in range(n):
        ans = (ans + a[i] * mod_combination(i, k-1, c_table)) % MOD

    a.sort(reverse=True)
    for i in range(n):
        ans = (ans - a[i] * mod_combination(i, k-1, c_table)) % MOD

    print(ans)


main()


Fixed submission:
import math

MOD = 10**9+7


def make_combination_table(n):
    fact = [1]
    for i in range(1, n+1):
        fact.append(fact[i-1] * i % MOD)

    ifact = [0] * (n+1)
    ifact[n] = pow(fact[n], MOD-2, MOD)
    for i in range(n, 0, -1):
        ifact[i-1] = ifact[i] * i % MOD
    return (fact, ifact)


def mod_combination(n, r, table):
    if r > n:
        return 0
    return table[0][n] * table[1][n - r] * table[1][r] % MOD


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    c_table = make_combination_table(n)

    a.sort()
    a_max = 0
    for i in range(n):
        a_max += a[i] * mod_combination(i, k-1, c_table) % MOD

    a.sort(reverse=True)
    a_min = 0
    for i in range(n):
        a_min += a[i] * mod_combination(i, k-1, c_table) % MOD

    print((a_max - a_min) % MOD)


main()

Buggy python submission (verdict: Time Limit Exceeded):
import math

MOD = 10**9+7


def mod_combination(n, r):
    if r > n:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r)) % MOD


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    ans = 0
    a.sort()
    for i in range(n):
        ans = (ans + a[i] * mod_combination(i, k-1)) % MOD

    a.sort(reverse=True)
    for i in range(n):
        ans = (ans-a[i] * mod_combination(i, k-1)) % MOD

    print(ans)


main()


Fixed submission:
import math

MOD = 10**9+7


def make_combination_table(n):
    fact = [1]
    for i in range(1, n+1):
        fact.append(fact[i-1] * i % MOD)

    ifact = [0] * (n+1)
    ifact[n] = pow(fact[n], MOD-2, MOD)
    for i in range(n, 0, -1):
        ifact[i-1] = ifact[i] * i % MOD
    return (fact, ifact)


def mod_combination(n, r, table):
    if r > n:
        return 0
    return table[0][n] * table[1][n - r] * table[1][r] % MOD


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    c_table = make_combination_table(n)

    a.sort()
    a_max = 0
    for i in range(n):
        a_max += a[i] * mod_combination(i, k-1, c_table) % MOD

    a.sort(reverse=True)
    a_min = 0
    for i in range(n):
        a_min += a[i] * mod_combination(i, k-1, c_table) % MOD

    print((a_max - a_min) % MOD)


main()
Buggy python submission (verdict: Runtime Error):
import statistics
import math

MOD = 10**9+7


def main():
    n = int(input())
    x = list(map(int, input().split()))

    c = 0
    t = 0
    for i in range(n-1):
        c += 1/(i+1) % MOD
        t += c * (x[i+1]-x[i])
        t %= MOD

    print(int(t * math.factorial(n-1) % MOD))


main()


Fixed submission:
import statistics
import math

MOD = 10**9+7


def main():
    n = int(input())
    x = list(map(int, input().split()))

    c = 0
    t = 0
    for i in range(n-1):
        c += pow(i+1, MOD-2, MOD)
        t += c * (x[i+1]-x[i])
        t %= MOD

    fact = math.factorial(n-1) % MOD
    print(t * fact % MOD)


main()

Buggy python submission (verdict: Runtime Error):
import statistics
import math


def main():
    n = int(input())
    x = list(map(int, input().split()))

    c = 0
    t = 0
    for i in range(n-1):
        c += 1/(i+1)
        t += c * (x[i+1]-x[i])
        t %= 10**9+7

    print(int(t * math.factorial(n-1) % (10**9+7)))


main()


Fixed submission:
import statistics
import math

MOD = 10**9+7


def main():
    n = int(input())
    x = list(map(int, input().split()))

    c = 0
    t = 0
    for i in range(n-1):
        c += pow(i+1, MOD-2, MOD)
        t += c * (x[i+1]-x[i])
        t %= MOD

    fact = math.factorial(n-1) % MOD
    print(t * fact % MOD)


main()

Buggy python submission (verdict: Runtime Error):
import statistics
import math


def main():
    n = int(input())
    x = list(map(int, input().split()))

    c = 0
    t = 0
    for i in range(n-1):
        c += 1/(i+1)
        t += c * (x[i+1]-x[i])
        t %= 10**9+7

    print(t * math.factorial(n-1) % (10**9+7))


main()


Fixed submission:
import statistics
import math

MOD = 10**9+7


def main():
    n = int(input())
    x = list(map(int, input().split()))

    c = 0
    t = 0
    for i in range(n-1):
        c += pow(i+1, MOD-2, MOD)
        t += c * (x[i+1]-x[i])
        t %= MOD

    fact = math.factorial(n-1) % MOD
    print(t * fact % MOD)


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


if __name__ == '__main__':
    n = int(input())

    if n < 3:
        print(0)
    else:
        count = 1
        n2=n-1
        for i in range(1,n2):
            count+=n2//i

    print(count)



Fixed submission:

if __name__ == '__main__':
    n = int(input())

    if n == 2:
        print(1)
    else:
        count = 1
        n2=n-1
        for i in range(1,n2):
            count+=n2//i
        print(count)
Buggy python submission (verdict: Time Limit Exceeded):
if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    mod = 10**9+7
    count = 0

    for i in range(n-1):
        for j in range(i+1,n):
            count += (a[i]*a[j])%mod
    print(count%mod)



Fixed submission:
if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    mod = 10**9+7
    sumA = sum(a)
    sumB = 0
    count = 0

    for i in range(n-1):
        sumB+=a[i]
        count += ((sumA-sumB)*a[i])%mod
    print(count%mod)
Buggy python submission (verdict: Time Limit Exceeded):
if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    a.sort(reverse=True)
    ans = 0
    dict = {}
    for i in a:
        if len(dict) > 0:
            ans+=max(dict)
            if dict[max(dict)] ==1:
                dict.pop(max(dict))
            else:
                dict[max(dict)]-=1
            if i in dict:
                dict[i]+=2
            else:
                dict[i]=2


        else:
            dict[i]=1


    print(ans)



Fixed submission:
if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    a.sort(reverse=True)
    ans = 0
    count = 0
    for i in a:
        if ans ==0:
            ans+=i
            count+=1
        else:
            if count == n-2:
                ans+=i
                break
            elif count == n-3:
                ans+=i*2
                break
            else:
                ans+=i*2
                count+=2

    if n ==2:
        ans= max(a)

    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    a.sort(reverse=True)
    ans = 0
    dict = {}
    for i in a:
        if len(dict) > 0:
            ans+=max(dict)
            if dict[max(dict)] ==1:
                dict.pop(max(dict))
            else:
                dict[max(dict)]-=1
            if i in dict:
                dict[i]+=2
            else:
                dict[i]=2


        else:
            dict[i]=1


    print(ans)



Fixed submission:
if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    a.sort(reverse=True)
    ans = 0
    count = 0
    for i in a:
        if ans ==0:
            ans+=i
            count+=1
        else:
            if count == n-2:
                ans+=i
                break
            elif count == n-3:
                ans+=i*2
                break
            else:
                ans+=i*2
                count+=2

    if n ==2:
        ans= max(a)

    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    a.sort(reverse=True)
    ans = 0
    list = []
    for i in a:
        if len(list) > 0:
            ans+=max(list)
            list.remove(max(list))
            list.append(i)
            list.append(i)
        else:
            list.append(i)


    print(ans)



Fixed submission:
if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    a.sort(reverse=True)
    ans = 0
    count = 0
    for i in a:
        if ans ==0:
            ans+=i
            count+=1
        else:
            if count == n-2:
                ans+=i
                break
            elif count == n-3:
                ans+=i*2
                break
            else:
                ans+=i*2
                count+=2

    if n ==2:
        ans= max(a)

    print(ans)
Buggy python submission (verdict: Runtime Error):
if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    q = int(input())
    key = [i for i in range(10**5+1)]
    val = [0]*(10**5+1)
    dict = dict(zip(key,val))
    dict.update(collections.Counter(a))
    ans = sum(a)

    for i in range(q):
        b, c = map(int, input().split())
        ans= ans - b*dict[b] + c*dict[b]
        count = dict[b]
        dict[b]=0
        dict[c]+=count
        print(ans)




Fixed submission:
import collections


if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    q = int(input())
    key = [i for i in range(10**5+1)]
    val = [0]*(10**5+1)
    dict = dict(zip(key,val))
    dict.update(collections.Counter(a))
    ans = sum(a)

    for i in range(q):
        b, c = map(int, input().split())
        ans= ans - b*dict[b] + c*dict[b]
        count = dict[b]
        dict[b]=0
        dict[c]+=count
        print(ans)

Buggy python submission (verdict: Runtime Error):

import collections


if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    q = int(input())
    key = [i for i in range(10**5)]
    val = [0]*(10**5)
    dict = dict(zip(key,val))
    dict.update(collections.Counter(a))
    ans = sum(a)

    for i in range(q):
        b, c = map(int, input().split())
        ans= ans - b*dict[b] + c*dict[b]
        count = dict[b]
        dict[b]=0
        dict[c]+=count
        print(ans)


Fixed submission:
import collections


if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    q = int(input())
    key = [i for i in range(10**5+1)]
    val = [0]*(10**5+1)
    dict = dict(zip(key,val))
    dict.update(collections.Counter(a))
    ans = sum(a)

    for i in range(q):
        b, c = map(int, input().split())
        ans= ans - b*dict[b] + c*dict[b]
        count = dict[b]
        dict[b]=0
        dict[c]+=count
        print(ans)

Buggy python submission (verdict: Runtime Error):

import collections


if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    q = int(input())
    key = [i for i in range(10**5)]
    val = [0]*(10**5)
    dict = dict(zip(key,val))
    dict.update(collections.Counter(a))
    ans = sum(a)

    for i in range(q):
        b, c = map(int, input().split())
        ans= ans - b*dict[b] + c*dict[b]
        count = dict[b]
        dict[b]=0
        dict[c]+=count
        print(ans)





Fixed submission:
import collections


if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    q = int(input())
    key = [i for i in range(10**5+1)]
    val = [0]*(10**5+1)
    dict = dict(zip(key,val))
    dict.update(collections.Counter(a))
    ans = sum(a)

    for i in range(q):
        b, c = map(int, input().split())
        ans= ans - b*dict[b] + c*dict[b]
        count = dict[b]
        dict[b]=0
        dict[c]+=count
        print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
if __name__ == '__main__':
    a, v = map(int, input().split())
    b, w = map(int, input().split())
    t = int(input())

    if w>= v:
        print("NO")
    else:
        flag = False
        if a == b:
            flag = True

        for i in range(t):
            if b>a:
                a+=v
                b+=w
            else:
                a-=v
                b-=w
            if a==b:
                flag=True
        if flag:
            print("YES")
        else:
            print("NO")



Fixed submission:
if __name__ == '__main__':
    a, v = map(int, input().split())
    b, w = map(int, input().split())
    t = int(input())
    l =abs(a - b)
    s=abs(v - w)

    if w >= v or l / s > t:
        print("NO")
    else:
        print("YES")