Codeforce:g. good key, bad key [greed]

analysis

There are two operations , We don't know which one to choose
Let's consider a after b And first b after a
# x y
# good and bad: x + y // 2 - k
# bad and good: x // 2 + y // 2 - k
# thus, after bad no good
# 2 ^ 30 > 10 ** 9, at most 30 bad

therefore ,bad Back root good All bad
therefore bad Continue the root later bad, most 30 individual , The back is full of 0

ac code

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n, k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    # x y
    # good and bad: x + y // 2 - k
    # bad and good: x // 2 + y // 2 - k
    # thus, after bad no good
    # 2 ^ 30 > 10 ** 9, at most 30 bad
    maxn = 0
    nowSum = 0
    for i in range(n):
        badSum = nowSum
        cnt = 0
        while cnt < 32 and i + cnt < n:
            badSum += a[i + cnt] // (2 ** (cnt + 1))
            cnt += 1
        maxn = max(maxn, badSum)
        nowSum += a[i] - k # goodSum

    maxn = max(maxn, nowSum)
    print(maxn)

summary

Found out bad Cannot root behind good It's done greedily