結果
問題 |
No.1231 Make a Multiple of Ten
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:46:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 86 ms / 2,000 ms |
コード長 | 1,279 bytes |
コンパイル時間 | 159 ms |
コンパイル使用メモリ | 82,044 KB |
実行使用メモリ | 106,980 KB |
最終ジャッジ日時 | 2025-03-20 20:46:49 |
合計ジャッジ時間 | 2,090 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
def main(): import sys input = sys.stdin.read data = input().split() N = int(data[0]) A = list(map(int, data[1:N+1])) sum_total = sum(A) sum_mod = sum_total % 10 if sum_mod == 0: print(N) return # Count occurrences of each mod 10 mod_counts = [0] * 10 for a in A: mod = a % 10 mod_counts[mod] += 1 # Generate items: (add_mod, cost) items = [] for x in range(10): cnt = mod_counts[x] if cnt == 0: continue max_k = min(cnt, 10) for k in range(1, max_k + 1): add_mod = (x * k) % 10 items.append((add_mod, k)) # DP initialization INF = float('inf') dp = [INF] * 10 dp[0] = 0 # Starting with 0 mod and 0 cost # Update DP with items for (add_mod, cost) in items: # Iterate in reverse to avoid reusing the same item multiple times for j in range(9, -1, -1): if dp[j] != INF: new_mod = (j + add_mod) % 10 if dp[new_mod] > dp[j] + cost: dp[new_mod] = dp[j] + cost if dp[sum_mod] == INF: print(0) else: print(N - dp[sum_mod]) if __name__ == '__main__': main()