結果

問題 No.2330 Eat Slime
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:25:17
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 997 bytes
コンパイル時間 312 ms
コンパイル使用メモリ 82,944 KB
実行使用メモリ 144,608 KB
最終ジャッジ日時 2025-03-31 17:25:50
合計ジャッジ時間 7,952 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
from collections import defaultdict

n, m, X = map(int, input().split())
C = list(map(int, input().split()))

# Preprocess positions for each color (1-based index)
pos = [[] for _ in range(6)]  # colors 1-5
for idx, c in enumerate(C, 1):  # idx is 1-based
    pos[c].append(idx)

sum_ab = defaultdict(int)
for _ in range(m):
    a, b, y = map(int, input().split())
    sum_ab[(a, b)] += y

Y = [0] * (n + 1)  # Y[k] for k in 0..n

# Process each (a, b) group and accumulate the contributions
for (a, b), total in sum_ab.items():
    if total == 0:
        continue
    pb = pos[b]
    if not pb:
        continue
    # Find the first index in pb that is >= a using bisect
    idx = bisect.bisect_left(pb, a)
    for i in pb[idx:]:
        k = i - a
        if 0 <= k <= n:
            Y[k] += total

# Compute the maximum score
max_score = 0
for k in range(n + 1):
    current_score = X * k + Y[k]
    if current_score > max_score:
        max_score = current_score

print(max_score)
0