結果
問題 |
No.910 素数部分列
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:43:23 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,533 bytes |
コンパイル時間 | 208 ms |
コンパイル使用メモリ | 82,728 KB |
実行使用メモリ | 89,916 KB |
最終ジャッジ日時 | 2025-03-20 20:44:11 |
合計ジャッジ時間 | 5,247 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 WA * 29 |
ソースコード
import bisect def main(): import sys n = int(sys.stdin.readline()) s = sys.stdin.readline().strip() # Step 1: Count 3,5,7 count_3 = 0 count_5 = 0 count_7 = 0 ones = [] nines = [] for idx, c in enumerate(s): if c == '3': count_3 +=1 elif c == '5': count_5 +=1 elif c == '7': count_7 +=1 else: if c == '1': ones.append(idx) else: assert c == '9' nines.append(idx) total = count_3 + count_5 + count_7 # Now, process remaining characters (1 and 9) # Compute max possible pairs of 19 and 11 via two schemes # Scheme A: prioritize 19 then 11 max_19_a = 0 j = 0 # Process ones and nines in order of their indices # Iterate through all 1's and find earliest possible 9 for i_idx in ones: # Find the first nine in nines >= i_idx, starting from j # Using binary search pos = bisect.bisect_left(nines, i_idx, j) if pos < len(nines): max_19_a +=1 j = pos +1 scheme_a = max_19_a + ( (len(ones) - max_19_a) //2 ) # Scheme B: prioritize 11 then 19 max_11_b = len(ones) // 2 remaining_1 = len(ones) %2 max_19_b = min(remaining_1, len(nines)) scheme_b = max_11_b + max_19_b remaining_total = max(scheme_a, scheme_b) total += remaining_total print(total) if __name__ == "__main__": main()