結果

問題 No.921 ずんだアロー
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:34:11
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 795 bytes
コンパイル時間 232 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 101,352 KB
最終ジャッジ日時 2025-04-16 00:35:52
合計ジャッジ時間 2,422 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
a = list(map(int, input().split()))

# Calculate the maximum sum of same-value blocks
from collections import defaultdict
sum_v = defaultdict(int)
if not a:
    print(0)
    exit()
current = a[0]
count = 1
for num in a[1:]:
    if num == current:
        count += 1
    else:
        sum_v[current] += count
        current = num
        count = 1
sum_v[current] += count  # Add the last block
max_sum = max(sum_v.values()) if sum_v else 0

# Calculate the maximum independent set using dynamic programming
dp0, dp1 = 0, 0  # dp0: not take current, dp1: take current
for num in a:
    new_dp0 = max(dp0, dp1)
    new_dp1 = dp0 + 1
    dp0, dp1 = new_dp0, new_dp1
max_independent = max(dp0, dp1)

# Determine the maximum of the two approaches
print(max(max_sum, max_independent))
0