結果

問題 No.1542 ぽんぽんぽん ぽんぽんぽんぽん ぽんぽんぽん
ユーザー lam6er
提出日時 2025-04-16 16:47:13
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,136 bytes
コンパイル時間 761 ms
コンパイル使用メモリ 81,768 KB
実行使用メモリ 61,996 KB
最終ジャッジ日時 2025-04-16 16:49:55
合計ジャッジ時間 2,882 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
s = input().strip()

# Initialize DP table
INF = -float('inf')
dp = [[INF] * 7 for _ in range(n + 1)]
dp[0][0] = 0  # start at position 0 with state 0 (no characters matched)

for i in range(n + 1):
    for state in range(7):
        if dp[i][state] == INF:
            continue
        
        # Option 1: Do not select a "pon" substring starting at i
        if i < n:
            current_char = s[i]
            new_state = state
            if state < 6:
                required = "ponpon"[state]
                if current_char == required:
                    new_state = state + 1
            if dp[i + 1][new_state] < dp[i][state]:
                dp[i + 1][new_state] = dp[i][state]
        
        # Option 2: Select a "pon" substring starting at i if possible
        if i + 2 < n:
            if s[i] == 'p' and s[i+1] == 'o' and s[i+2] == 'n':
                new_i = i + 3
                new_count = dp[i][state] + 1
                if new_i <= n and dp[new_i][state] < new_count:
                    dp[new_i][state] = new_count

max_k = dp[n][6]
if max_k != INF:
    print(max_k)
else:
    print(-1)
0