Ba lô chia hết

Buổi 71-72 — Ôn tập Dynamic Programming
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho $N$ món đồ, món thứ $i$ có giá trị $v_i$. Bạn cần chọn ra một tập con khác rỗng các món đồ sao cho tổng giá trị của chúng chia hết cho $K$ và đạt giá trị lớn nhất có thể. Nếu không có cách chọn nào thỏa mãn, in ra -1.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N, K$ ($1 \le N \le 1000, 1 \le K \le 100$).
  • Dòng thứ hai chứa $N$ số nguyên $v_1, v_2, \dots, v_N$ ($1 \le v_i \le 10^9$).
Dữ liệu ra
  • Tổng giá trị lớn nhất chia hết cho $K$, hoặc -1.
Ví dụ
Input Output
4 5
4 3 2 6
15
Giới hạn
  • $1 \le N \le 1000, 1 \le K \le 100$
Draft saved