結果

問題 No.1512 作文
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:49:59
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,259 bytes
コンパイル時間 231 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 140,592 KB
最終ジャッジ日時 2025-06-12 13:50:21
合計ジャッジ時間 5,981 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 24 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def is_good(s):
    for i in range(1, len(s)):
        if s[i] < s[i-1]:
            return False
    return True

def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    strings = input[1:n+1]
    
    good_strings = []
    for s in strings:
        if is_good(s):
            good_strings.append(s)
    
    if not good_strings:
        print(0)
        return
    
    data = []
    for s in good_strings:
        c_start = s[0]
        c_end = s[-1]
        length = len(s)
        data.append((c_start, c_end, length))
    
    data.sort(key=lambda x: x[1])
    sorted_ces = [d[1] for d in data]
    n = len(data)
    
    dp = [0] * n
    max_dps = [0] * n
    
    for i in range(n):
        c_start_i = data[i][0]
        len_i = data[i][2]
        
        pos = bisect.bisect_right(sorted_ces, c_start_i, 0, i)
        j = pos - 1
        
        if j >= 0:
            candidate = max_dps[j] + len_i
        else:
            candidate = len_i
        
        dp_i = max(candidate, len_i)
        dp[i] = dp_i
        
        if i == 0:
            max_dps[i] = dp_i
        else:
            max_dps[i] = max(max_dps[i-1], dp_i)
    
    print(max_dps[-1])

if __name__ == "__main__":
    main()
0