結果
問題 |
No.2321 Continuous Flip
|
ユーザー |
![]() |
提出日時 | 2025-06-12 20:03:23 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,442 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 82,452 KB |
実行使用メモリ | 52,352 KB |
最終ジャッジ日時 | 2025-06-12 20:08:38 |
合計ジャッジ時間 | 6,357 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | TLE * 1 -- * 29 |
ソースコード
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]) - 1 # converting to 0-based index idx += 1 R = int(data[idx]) - 1 idx += 1 operations.append((L, R)) # Compute the gain for each operation gains = [] for L, R in operations: total = sum(A[L:R+1]) gain = total - C gains.append(gain) # Sort operations based on the maximum gain sorted_ops = sorted([(gains[i], operations[i]) for i in range(M)], key=lambda x: (-x[0], x[1][0])) # Simulate the greedy selection current_state = [0] * N total_gain = 0 included = [] for gain, (L, R) in sorted_ops: # Calculate the actual gain if we include this operation actual = 0 for i in range(L, R+1): if current_state[i] == 0: actual += A[i] else: actual -= A[i] actual -= C if actual > 0: total_gain += actual for i in range(L, R+1): current_state[i] ^= 1 included.append((L, R)) print(total_gain) if __name__ == '__main__': main()