結果
問題 | No.2330 Eat Slime |
ユーザー |
![]() |
提出日時 | 2023-05-24 11:16:23 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 2,108 ms / 4,000 ms |
コード長 | 878 bytes |
コンパイル時間 | 151 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 110,052 KB |
最終ジャッジ日時 | 2024-12-23 15:14:12 |
合計ジャッジ時間 | 48,341 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
import numpy as npdef convolve(f, g):fft_len = 1while 2 * fft_len < len(f) + len(g) - 1:fft_len *= 2fft_len *= 2Ff = np.fft.rfft(np.array(f, np.int64), fft_len)Fg = np.fft.rfft(np.array(g, np.int64), fft_len)Fh = Ff * Fgh = np.fft.irfft(Fh, fft_len)h = np.rint(h).astype(np.int64)return h[:len(f) + len(g) - 1]n, m, x = map(int, input().split())c = list(map(int, input().split()))color = [[0] * n for _ in range(5)]point = [[0] * n for _ in range(5)]for i in range(n):color[c[i] - 1][i] += 1for _ in range(m):a, b, y = map(int, input().split())point[b - 1][n - a] += yscore_f = [convolve(color[i], point[i])[n - 1:] for i in range(5)]score = [score_f[0][i] + score_f[1][i] + score_f[2][i] + score_f[3][i] + score_f[4][i]for i in range(n)]ans = x * nfor i in range(n):ans = max(ans, i * x + score[i])print(ans)