結果

問題 No.2330 Eat Slime
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 12:58:17
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,652 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 158,636 KB
最終ジャッジ日時 2025-06-12 13:05:15
合計ジャッジ時間 6,590 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    n = int(data[ptr])
    ptr += 1
    m = int(data[ptr])
    ptr += 1
    x = int(data[ptr])
    ptr += 1
    
    C = list(map(int, data[ptr:ptr+n]))
    ptr += n
    
    sum_ab = defaultdict(lambda: defaultdict(int))
    for _ in range(m):
        a = int(data[ptr])
        ptr += 1
        b = int(data[ptr])
        ptr += 1
        y = int(data[ptr])
        ptr += 1
        sum_ab[a][b] += y
    
    # Preprocess positions for each color (1-based)
    positions = [[] for _ in range(6)]  # colors 1-5
    for idx in range(n):
        c = C[idx]
        positions[c].append(idx + 1)  # 1-based position
    
    total = [0] * (n + 1)  # total[K] for K from 0 to n
    
    # Iterate through all a and c in sum_ab
    for a in list(sum_ab.keys()):
        for c in list(sum_ab[a].keys()):
            y_sum = sum_ab[a][c]
            if y_sum == 0:
                continue
            pos_list = positions[c]
            if not pos_list:
                continue
            # Find the first position >= a
            idx = bisect.bisect_left(pos_list, a)
            for i in range(idx, len(pos_list)):
                pos = pos_list[i]
                K = pos - a
                if K > n:
                    break  # pos <=n, so K = pos -a <=n -a <=n
                total[K] += y_sum
    
    max_score = 0
    for K in range(n + 1):
        current = x * K + total[K]
        if current > max_score:
            max_score = current
    print(max_score)

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