結果
問題 |
No.2204 Palindrome Splitting (No Rearrangement ver.)
|
ユーザー |
|
提出日時 | 2023-02-03 22:12:18 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 623 bytes |
コンパイル時間 | 176 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 82,944 KB |
最終ジャッジ日時 | 2024-07-02 20:13:21 |
合計ジャッジ時間 | 27,150 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 TLE * 2 -- * 3 |
ソースコード
S=input() n=len(S) DP=[1 for _ in range(n+1)] DP[0]=len(S) s_to_n={chr(i+97):i for i in range(26)} def is_kaibun(s): n=len(s) for i in range(n//2): if s[i]!=s[n-1-i]: return 0 return 1 for i in range(n): cnt=1<<s_to_n[S[i]] for j in range(i+1,n): s=S[j] cnt^=1<<s_to_n[s] if (j+i)%2==0 and cnt^(1<<s_to_n[S[(i+j)//2]])==0: if is_kaibun(S[i:j+1]): DP[j+1]=max(min(DP[i],j-i+1),DP[j+1]) elif (j+i)%2==1 and cnt==0: if is_kaibun(S[i:j+1]): DP[j+1]=max(min(DP[i],j-i+1),DP[j+1]) print(DP[-1])