結果

問題 No.2330 Eat Slime
ユーザー tyawanmusi
提出日時 2023-05-26 09:31:35
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,603 bytes
コンパイル時間 219 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 132,876 KB
最終ジャッジ日時 2024-12-24 19:14:19
合計ジャッジ時間 121,008 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 TLE * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import cmath
pi = cmath.pi
exp = cmath.exp


def make_exp_t(N, base):
  exp_t = {0: 1}
  temp = N
  while temp:
    exp_t[temp] = exp(base / temp)
    temp >>= 1
  return exp_t


def fft_dfs(f, s, N, st, exp_t):
  if N == 2:
    a = f[s]; b = f[s + st]
    return [a + b, a - b]
  N2 = N // 2; st2 = st * 2
  F0 = fft_dfs(f, s, N2, st2, exp_t)
  F1 = fft_dfs(f, s + st, N2, st2, exp_t)
  w = exp_t[N]; wk = 1.0
  for k in range(N2):
    U = F0[k]; V = wk * F1[k]
    F0[k] = U + V
    F1[k] = U - V
    wk *= w
  F0.extend(F1)
  return F0


def fft(f, N):
  if N == 1:
    return f
  return fft_dfs(f, 0, N, 1, fft_exp_t)


def ifft(F, N):
  if N == 1:
    return F
  f = fft_dfs(F, 0, N, 1, ifft_exp_t)
  for i in range(N):
    f[i] /= N
  return f


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] += 1
for _ in range(m):
  a, b, y = map(int, input().split())
  point[b - 1][n - a] += y

N = 2**(2 * len(color[0]) - 1).bit_length()
fft_exp_t = make_exp_t(N, -2j * pi)
ifft_exp_t = make_exp_t(N, 2j * pi)

score_f = []
for i in range(5):
  f = color[i]
  g = point[i]
  f.extend([0] * (N - len(f)))
  g.extend([0] * (N - len(g)))
  F = fft(f, N)
  G = fft(g, N)
  fg = ifft([a * b for a, b in zip(F, G)], N)[n - 1:]
  score_f.append(list(map(lambda x: int(x.real + 0.5), fg)))
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 * n
for i in range(n):
  ans = max(ans, i * x + score[i])
print(ans)
0