結果

問題 No.1512 作文
ユーザー lam6er
提出日時 2025-04-15 22:13:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 955 bytes
コンパイル時間 384 ms
コンパイル使用メモリ 82,284 KB
実行使用メモリ 121,640 KB
最終ジャッジ日時 2025-04-15 22:14:38
合計ジャッジ時間 4,818 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
good_strings = []

for _ in range(n):
    s = input().strip()
    valid = True
    for i in range(1, len(s)):
        if s[i] < s[i-1]:
            valid = False
            break
    if valid:
        if len(s) == 0:
            continue  # though per problem statement, S_i has length >=1
        first = s[0]
        last = s[-1]
        good_strings.append((first, last, len(s)))

# Initialize dp and max_dp
dp = [0] * 26
max_dp = [0] * 26

for first, last, length in good_strings:
    f_idx = ord(first) - ord('a')
    l_idx = ord(last) - ord('a')
    
    current_max = max_dp[f_idx]
    candidate = current_max + length
    
    if candidate > dp[l_idx]:
        dp[l_idx] = candidate
        
        # Recompute max_dp
        current_max_dp = dp[0]
        max_dp[0] = current_max_dp
        for i in range(1, 26):
            current_max_dp = max(current_max_dp, dp[i])
            max_dp[i] = current_max_dp

print(max_dp[-1])
0