結果
問題 |
No.1515 Making Many Multiples
|
ユーザー |
![]() |
提出日時 | 2025-04-16 16:40:39 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,712 bytes |
コンパイル時間 | 237 ms |
コンパイル使用メモリ | 82,120 KB |
実行使用メモリ | 66,284 KB |
最終ジャッジ日時 | 2025-04-16 16:41:26 |
合計ジャッジ時間 | 3,753 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 3 |
other | AC * 2 TLE * 1 -- * 25 |
ソースコード
import sys def main(): input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]); ptr += 1 K = int(input[ptr]); ptr += 1 X = int(input[ptr]); ptr += 1 Y = int(input[ptr]); ptr += 1 A = list(map(int, input[ptr:ptr+N])) ptr += N x = X % K y = Y % K a, b = sorted((x, y)) current_dp = [[-1] * K for _ in range(K)] current_dp[a][b] = 0 for card in A: c = card % K next_dp = [[-1] * K for _ in range(K)] for a_prev in range(K): for b_prev in range(a_prev, K): if current_dp[a_prev][b_prev] == -1: continue current_score = current_dp[a_prev][b_prev] sum_three = (a_prev + b_prev + c) % K new_score = current_score + (1 if sum_three == 0 else 0) # Discard a_prev new_a = min(b_prev, c) new_b = max(b_prev, c) if next_dp[new_a][new_b] < new_score: next_dp[new_a][new_b] = new_score # Discard b_prev new_a = min(a_prev, c) new_b = max(a_prev, c) if next_dp[new_a][new_b] < new_score: next_dp[new_a][new_b] = new_score # Discard c new_a = a_prev new_b = b_prev if next_dp[new_a][new_b] < new_score: next_dp[new_a][new_b] = new_score current_dp = next_dp max_score = 0 for a in range(K): for b in range(a, K): if current_dp[a][b] > max_score: max_score = current_dp[a][b] print(max_score) if __name__ == "__main__": main()