Codeforces Round #804 (Div. 2)
4 өдрийн дараа |
B. "OR" тоглоом
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Чамд $a_{1}, a_{2}, ..., a_{n}$ гэсэн $n$ ширхэг тоо өгөгдөнө. Чи хамгийн олондоо $k$ үйлдэл хийж чадна. Үйлдэл бүрт аль нэг тоог $x$-ээр үржүүлж чадна. Бид $a_1 |\ a_2 |\ ...\ |\ a_n$-ийг аль болох их байлгахыг хүсч байгаа. Энд $|$-аар хоёртын OR үйлдлийг тэмдэглэв.
Чи хамгийн ихдээ $k$ үйлдэл хийж чадах бол $a_1 |\ a_2 |\ ...\ |\ a_n$-ийг хамгийн ихдээ хэд болгож чадах вэ?
Оролт
Эхний мөрөнд $n$, $k$, $x$ ($1 ≤ n ≤ 200 000$, $1 ≤ k ≤ 10$, $2 ≤ x ≤ 8$) гэсэн гурван бүхэл тоо өгөгдөнө.
Дараагийн мөрөнд $a_{1}, a_{2}, ..., a_{n}$ ($0 ≤ a_{i} ≤ 10^{9}$) гэсэн $n$ ширхэг бүхэл тоо байна .
Гаралт
Үүсч болох хамгийн их утгыг хэвлэ.
Орчуулсан: Бат-Од
Жишээ тэстүүд
Оролт
3 1 2 1 1 1
Гаралт
3
Оролт
4 2 3 1 2 4 8
Гаралт
79
Тэмдэглэл
Эхний жишээнд ямар ч үйлдэл хийсэн $1$, $1$, $2$ гэсэн гурван тоо үүсэх тул хариу $1\ |\ 1\ |\ 2 = 3$ байна.
Хоёр дахь жишээнд хэрэв бид $8$-ийг $3$-аар хоёр удаа үржүүлбэл $72$ гэсэн тоо гарна. Энэ тохиолдолд тоонууд $1$, $2$, $4$, $72$ болох ба OR үйлдлээр $79$ гэсэн утга гаргана. Энэ нь байж болох хамгийн их утга юм.