結果
問題 | No.464 PPAP |
ユーザー |
![]() |
提出日時 | 2016-11-25 18:24:57 |
言語 | PyPy2 (7.3.15) |
結果 |
AC
|
実行時間 | 168 ms / 2,000 ms |
コード長 | 1,104 bytes |
コンパイル時間 | 1,763 ms |
コンパイル使用メモリ | 76,672 KB |
実行使用メモリ | 78,848 KB |
最終ジャッジ日時 | 2024-11-27 14:35:18 |
合計ジャッジ時間 | 4,913 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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 = raw_input()n = len(s)rads = manachar(s)def is_palindrome(l, r):return rads[l + r] >= r - l + 1p1 = []for i in xrange(n - 3):if is_palindrome(0, i):p1.append(i)p2 = [0] * nfor i in p1:for j in xrange(i + 1, n - 2):if is_palindrome(i + 1, j):p2[j] += 1sum_p2 = [0] * nfor i in xrange(n - 1):sum_p2[i + 1] = sum_p2[i] + p2[i]ans = 0for k in xrange(2, n - 1):if is_palindrome(k + 1, n - 1):ans += sum_p2[k]print(ans)if __name__ == '__main__':solve()