結果

問題 No.2330 Eat Slime
ユーザー tyawanmusityawanmusi
提出日時 2023-05-26 09:32:35
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,603 bytes
コンパイル時間 373 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 61,908 KB
最終ジャッジ日時 2024-06-07 00:02:07
合計ジャッジ時間 6,520 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 35 ms
61,908 KB
testcase_01 AC 35 ms
53,540 KB
testcase_02 AC 36 ms
53,732 KB
testcase_03 AC 37 ms
53,640 KB
testcase_04 AC 35 ms
54,448 KB
testcase_05 AC 33 ms
53,332 KB
testcase_06 AC 35 ms
54,748 KB
testcase_07 TLE -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
権限があれば一括ダウンロードができます

ソースコード

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