Nhận xét

• Phương án tối ưu nhất là đổi ~a_i~ thành ~0~

Subtask 1

• Quay lui các trạng thái ~0~ tương ứng giữ nguyên ~a_i~ và ~1~ tương ứng với biến đổi ~a_i = 0~
• Lấy kết quả nhỏ nhất của các trang thái thoả mãn

Độ phức tạp ~\mathcal O(2^{20})~

Subtask 3

• Gọi ~dp_i~ là chi phí thấp nhất để ~a_j\&a_{j+1}\&...\&a_{j+k-1} = 0~ với mọi ~1 \le i \le n-k+1~ và ~1 \le j \le i~
• ~dp_i = dp_{i-1}~ nếu ~a_j\&a_{j+1}\&...\&a_{j+k-1} = 0~
• ~dp_i = min(dp_i, c_j + dp_{j-k}~) nếu ~k \le j \le i+k-1~, nếu ~j < k~ thì ~dp_i = min(dp_i, c_j)~

Độ phức tạp ~\mathcal O(N*K)~

Subtask 4

• Tư tưởng như subtask 3 dùng Segment tree để tính nhanh giá trị AND của một đoạn sử dụng deque để tính nhanh
  • ~dp_i = min(dp_i, c_j + dp_{j-k}~) nếu ~k \le j \le i+k-1~, nếu ~j < k~ thì ~dp_i = min(dp_i, c_j)~

Độ phức tạp ~\mathcal O(N*logN)~