Tập Con Giàu Có Nhất

Buổi 23 — Thao tác bit
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Submissions
Đề bài

Cho $N$ vật phẩm, mỗi vật có giá trị $v_i$. Cho một bitmask $M$ biểu diễn các vật phẩm được phép chọn (bit thứ $i$ bằng $1$ nghĩa là vật $i$ được phép). Trong tất cả các tập con của tập các vật phẩm được phép, hãy tìm tổng giá trị lớn nhất của tập con có tổng giá trị không vượt quá $W$.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $W$.
  • Dòng thứ hai chứa $N$ số nguyên $v_1, v_2, \ldots, v_N$.
  • Dòng thứ ba chứa số nguyên $M$ — bitmask các vật phẩm được phép.
Dữ liệu ra
  • In ra tổng giá trị lớn nhất không vượt quá $W$.
Ví dụ
Input Output
4 10
3 5 7 2
13
10
Giới hạn
  • $1 \le N \le 20$
  • $1 \le W \le 10^9$
  • $1 \le v_i \le 10^9$
  • $0 \le M < 2^N$
Draft saved