結果
問題 | No.464 PPAP |
ユーザー |
![]() |
提出日時 | 2016-11-25 18:19:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 145 ms / 2,000 ms |
コード長 | 1,172 bytes |
コンパイル時間 | 457 ms |
コンパイル使用メモリ | 82,132 KB |
実行使用メモリ | 76,460 KB |
最終ジャッジ日時 | 2024-11-27 14:34:03 |
合計ジャッジ時間 | 2,523 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 22 |
ソースコード
def manachar(s):def get(i):return '^' if i & 1 else s[i>>1]size = len(s) * 2 - 1rads = [0] * sizei = j = 0while i < size:while i - j >= 0 and i + j < size and get(i - j) == get(i + j):j += 1rads[i] = jk = 1while i - k >= 0 and i + k < size and k + rads[i - k] < j:rads[i + k] = rads[i - k]k += 1i += kj -= kreturn radsdef solve():s = input()n = len(s)assert 4 <= n <= 5000assert all('a' <= c <= 'z' for c in s)rads = manachar(s)def is_palindrome(l, r):return rads[l + r] >= r - l + 1p1 = []for i in range(n - 3):if is_palindrome(0, i):p1.append(i)p2 = [0] * (n - 1)for i in p1:for j in range(i + 1, n - 2):if is_palindrome(i + 1, j):p2[j] += 1sum_p2 = [0] * nfor i in range(n - 1):sum_p2[i + 1] = sum_p2[i] + p2[i]ans = 0for k in range(2, n - 1):if is_palindrome(k + 1, n - 1):ans += sum_p2[k]print(ans)if __name__ == '__main__':solve()