結果

問題 No.2321 Continuous Flip
ユーザー gew1fw
提出日時 2025-06-12 20:03:38
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,555 bytes
コンパイル時間 220 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 162,888 KB
最終ジャッジ日時 2025-06-12 20:09:02
合計ジャッジ時間 4,965 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    C = int(data[idx])
    idx += 1

    A = list(map(int, data[idx:idx+N]))
    idx += N

    operations = []
    for _ in range(M):
        L = int(data[idx])
        idx += 1
        R = int(data[idx])
        idx += 1
        operations.append((L-1, R-1))  # converting to 0-based

    # Precompute prefix sums for A
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i+1] = prefix[i] + A[i]

    # Function to compute sum of A[L..R]
    def sum_A(L, R):
        return prefix[R+1] - prefix[L]

    # Calculate the gain for each operation
    gains = []
    for L, R in operations:
        s = sum_A(L, R)
        gains.append((s - C, L, R))

    # Sort operations by gain in descending order
    gains.sort(reverse=True)

    # Initialize variables
    flipped = [False] * N
    current_sum = 0
    X = 0

    for g, L, R in gains:
        if g <= 0:
            break
        # Calculate the current sum of the interval
        total = 0
        for i in range(L, R + 1):
            if flipped[i]:
                total -= A[i]
            else:
                total += A[i]
        actual_gain = total - C
        if actual_gain > 0:
            # Perform the flip
            X += 1
            current_sum += actual_gain
            for i in range(L, R + 1):
                flipped[i] = not flipped[i]

    print(current_sum)

if __name__ == '__main__':
    main()
0