結果

問題 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
ユーザー gew1fw
提出日時 2025-06-12 19:57:15
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,471 bytes
コンパイル時間 294 ms
コンパイル使用メモリ 82,644 KB
実行使用メモリ 84,608 KB
最終ジャッジ日時 2025-06-12 19:58:43
合計ジャッジ時間 4,529 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    S = sys.stdin.readline().strip()
    n = len(S)
    if n < 4:
        print(0)
        return

    # Precompute is_p1: is_p1[i] is True if S[0..i] is a palindrome
    is_p1 = [False] * n
    for i in range(n):
        substr = S[:i+1]
        if substr == substr[::-1]:
            is_p1[i] = True

    # Precompute is_p3: is_p3[k] is True if S[k..n-1] is a palindrome
    is_p3 = [False] * n
    for k in range(n):
        substr = S[k:]
        if substr == substr[::-1]:
            is_p3[k] = True

    # Compute sum_p3_suffix: sum_p3_suffix[j] is the number of k >=j where is_p3[k] is True
    sum_p3_suffix = [0] * (n + 2)
    for j in range(n, -1, -1):
        if j < n:
            sum_p3_suffix[j] = sum_p3_suffix[j + 1] + (1 if is_p3[j] else 0)
        else:
            sum_p3_suffix[j] = 0

    total = 0

    # Precompute all possible j and count for each j
    for j in range(n):
        # For each j, count the number of valid i's where i <= j-1, is_p1[i] is True, and S[i+1..j] is a palindrome
        cnt_p2 = 0
        for i in range(j):
            if is_p1[i]:
                substr = S[i+1:j+1]
                if substr == substr[::-1]:
                    cnt_p2 += 1
        # Compute the number of valid k's for this j
        if j + 2 <= n - 1:
            cnt_p3 = sum_p3_suffix[j + 2]
        else:
            cnt_p3 = 0
        total += cnt_p2 * cnt_p3

    print(total)

if __name__ == "__main__":
    main()
0