AND Table

View as PDF

Submit solution

Points: 0.00 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Trước khi tham gia buổi Đại Hòa Nhạc, Gấu Trắng cần tìm cho mình một bản nhạc hoàn hảo nhất để trình diễn. Nhưng sau khi tham khảo rất nhiều nơi, Gấu Trắng nhận ra rằng bản nhạc hoàn hảo nhất phải được chính mình sáng tác nên. Vậy nên cậu đã bắt tay vào sáng tác ra bản nhạc của đời mình!

Biết được từ bài ~3~ rằng khuông nhạc trong Thế Giới Âm Nhạc là một bảng hai chiều, Gấu Trắng quyết định nghiên cứu về cấu trúc này.

Gấu Trắng định nghĩa "độ hoàn hảo" của một bảng hai chiều là tổng bitwise AND~^\dagger~ lớn nhất trong một bảng con của bảng ban đầu, sao cho bảng con này có số lượng phần tử (hay diện tích) nằm trong khoảng cho trước.

Gấu Trắng luyện tập bằng một bài tập như sau: Cho một bảng hai chiều có kích thước ~n \times m~ và hai số nguyên ~L, R~. Hãy tính độ hoàn hảo của bảng này.

Nói cách khác, Gấu Trắng sẽ tìm hình chữ nhật con có diện tích trong khoảng ~[L, R]~ sao cho tổng bitwise AND của các phần tử thuộc hình chữ nhật con đó là lớn nhất.

~^\dagger~ Phép bitwise AND của hai số nguyên, ký hiệu là ~a \mathbin{\&} b~, cho ra một số nguyên ~c~ sao cho trong biểu diễn nhị phân, mỗi bit (chữ số) của ~c~ là tích của hai chữ số tương ứng của ~a~ và ~b~. Ví dụ, ~206 \mathbin{\&} 101 = 68~ vì trong biểu diễn nhị phân, ta có:

  • ~1100 1110_2 = 206~ (giá trị ~206~ biểu diễn trong hệ nhị phân là dãy bit ~1100 1110~).
  • ~0110 0101_2 = 101~.
  • ~0100 0100_2 = 68~.
  • ~1100 1110_2 \mathbin{\&} 0110 0101_2 = 0100 0100_2~.

~^\dagger~Tổng bitwise AND của một dãy số ~a_1, a_2, a_3, \cdots, a_p~ là ~a_1 \mathbin{\&} a_2 \mathbin{\&} a_3 \mathbin{\&} \cdots \mathbin{\&} a_p~.

Input

  • Dòng đầu chứa bốn số nguyên ~n, m, L, R~ (~1 \leq n, m \leq 1000~, ~1 \leq L \leq R \leq n \times m~).

  • ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~m~ số nguyên ~a_{i, 1}, a_{i, 2}, \cdots, a_{i, m}~ (~0 \leq a_{i, j} \leq 10^9~).

Output

In ra độ hoàn hảo của bảng.

Scoring

  • Subtask ~1~ (~15\%~): ~1 \leq n, m \leq 50~.

  • Subtask ~2~ (~15\%~): ~1 \leq n, m \leq 300~.

  • Subtask ~3~ (~20\%~): ~1 \leq n, m \leq 1000~ và ~R = n \times m~.

  • Subtask ~4~ (~20\%~): ~1 \leq n, m \leq 1000~ và ~0 \leq a_{i, j} \leq 1~.

  • Subtask ~5~ (~30\%~): Không có giới hạn gì thêm.

Sample Input 1

6 4 4 10
7 11 27 31
8 15 3 19
15 20 5 2
16 22 15 6
29 13 21 1
10 20 25 30

Sample Output 1

4

Notes

Ví dụ, với bảng nhạc mà Gấu Trắng tự sáng tác như trên, độ hoàn hảo chính là bitwise AND của hình chữ nhật con có góc trên trái là ô ~(3, 2)~ và góc dưới phải là ô ~(5, 3)~.

Diện tích của hình chữ nhật này là ~6~ nằm trong khoảng ~[4, 10]~ và bitwise AND là ~20 \space \& \space 5 \space \& \space 22 \space \& \space 15 \space \& \space 13 \space \& \space 21 = 4~.

Lưu ý: ô ở dòng thứ ~i~, cột thứ ~j~ có tọa độ là ~(i, j)~ và có giá trị là ~a_{i, j}~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.