結果
問題 | No.464 PPAP |
ユーザー |
![]() |
提出日時 | 2016-11-25 18:23:30 |
言語 | Python2 (2.7.18) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,104 bytes |
コンパイル時間 | 620 ms |
コンパイル使用メモリ | 7,040 KB |
実行使用メモリ | 7,040 KB |
最終ジャッジ日時 | 2024-11-27 14:35:04 |
合計ジャッジ時間 | 6,502 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 TLE * 1 |
ソースコード
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()