結果
問題 | No.2204 Palindrome Splitting (No Rearrangement ver.) |
ユーザー |
|
提出日時 | 2023-02-03 22:20:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 709 ms / 2,000 ms |
コード長 | 809 bytes |
コンパイル時間 | 145 ms |
コンパイル使用メモリ | 82,400 KB |
実行使用メモリ | 315,648 KB |
最終ジャッジ日時 | 2024-07-02 20:23:50 |
合計ジャッジ時間 | 4,621 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
import syssys.setrecursionlimit(5*10**5)input = sys.stdin.readlinefrom collections import defaultdict, deque, Counterfrom heapq import heappop, heappushfrom bisect import bisect_left, bisect_rightfrom math import gcds = list(input().rstrip())n = len(s)dr = [[] for i in range(n)]for i in range(n):l, r= i,ifor j in range(n):ll = l-jrr = r+jif ll < 0 or rr >= n: breakif s[ll] == s[rr]:dr[rr].append(ll)else:breakfor i in range(n-1):l, r = i, i+1for j in range(n):ll = l-jrr = r+jif ll < 0 or rr >= n: breakif s[ll] == s[rr]:dr[rr].append(ll)else:breakdp = [1]*(n)for i in range(1, n):for j in dr[i]:if j == 0:dp[i] = i+1else:dp[i] = max(dp[i],min(i-j+1, dp[j-1]))print(dp[-1])