結果

問題 No.464 PPAP
ユーザー lam6er
提出日時 2025-03-20 18:46:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,642 ms / 2,000 ms
コード長 1,576 bytes
コンパイル時間 304 ms
コンパイル使用メモリ 82,732 KB
実行使用メモリ 468,716 KB
最終ジャッジ日時 2025-03-20 18:47:33
合計ジャッジ時間 13,457 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

S = input().strip()
n = len(S)

# Precompute is_palin[i][j] for all i <= j
is_palin = [[False] * n for _ in range(n)]
for i in range(n-1, -1, -1):
    for j in range(i, n):
        if i == j:
            is_palin[i][j] = True
        elif i + 1 == j:
            is_palin[i][j] = (S[i] == S[j])
        else:
            is_palin[i][j] = (S[i] == S[j] and is_palin[i+1][j-1])

# Precompute P1_ok: P1_ok[a] is True if S[0..a] is palindrome and a <= n-4
P1_ok = [False] * n
for a in range(n):
    if a <= n - 4 and is_palin[0][a]:
        P1_ok[a] = True

# Precompute P3_ok: P3_ok[c] is True if S[c+1..n-1] is palindrome and c <= n-2
P3_ok = [False] * n
for c in range(n):
    if c <= n - 2:
        start = c + 1
        end = n - 1
        if start <= end and is_palin[start][end]:
            P3_ok[c] = True

# Precompute sum_a[a][b] for each a, the count of valid b's up to position b (a+1 <= b)
sum_a = [[0]*n for _ in range(n)]
for a in range(n):
    sum_so_far = 0
    for b in range(n):
        if b < a + 1:
            sum_a[a][b] = 0
        else:
            if is_palin[a+1][b]:
                sum_so_far += 1
            sum_a[a][b] = sum_so_far

# Calculate the answer by iterating all valid a and c pairs
ans = 0
for a in range(n):
    if not P1_ok[a]:
        continue
    # Iterate c from a+2 to n-2 (inclusive)
    for c in range(a + 2, n - 1):  # since n-1 is not included in the range
        if c > n - 2:
            continue
        if not P3_ok[c]:
            continue
        current_count = sum_a[a][c - 1]
        ans += current_count

print(ans)
0