結果
問題 | No.2204 Palindrome Splitting (No Rearrangement ver.) |
ユーザー |
|
提出日時 | 2023-02-04 17:08:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 779 ms / 2,000 ms |
コード長 | 767 bytes |
コンパイル時間 | 159 ms |
コンパイル使用メモリ | 82,528 KB |
実行使用メモリ | 311,040 KB |
最終ジャッジ日時 | 2024-07-03 14:07:55 |
合計ジャッジ時間 | 4,832 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
S = input()N = len(S)l = [[] for _ in range(N)]for i in range(N):delta = 0while True:if i - delta >= 0 and i + delta < N:if S[i - delta] == S[i + delta]:l[i - delta].append(i + delta)else:breakelse:breakdelta += 1delta = 0while True:if i - delta >= 0 and i + 1 + delta < N:if S[i - delta] == S[i + delta + 1]:l[i - delta].append( i + 1 + delta)else:breakelse:breakdelta += 1dp = [0] * (N + 1)dp[0] = 10 ** 6for i in range(N):m = dp[i]for j in l[i]:t = min(m,j - i + 1)dp[j + 1] = max(dp[j + 1],t)print(dp[-1])