Elearning CodePath – CTP Online Judge

ẢNH ĐẸP

PICTURE

🟢 Hard

Khán đài của sân vận động Mỹ Đình có thể coi như một hình chữ nhật kích thước $m \times n$ có hướng Bắc – Nam, Đông – Tây. Ghế thứ $i$ từ phía Bắc và $j$ từ phía Tây được gọi là ghế $(i,j)$.

Hôm nay, ngày mồng 1 tết Nhâm Dần, tại sân Mỹ Đình diễn ra trận bóng Việt Nam – Trung Quốc; vì vậy tất cả các ghế đều có người ngồi, người ngồi ở ghế $(i,j)$ mặc áo màu $a_{i,j}$.

Tuấn sử dụng flycam để chụp các bức ảnh khán giả, tuy nhiên do hạn chế kĩ thuật nên chiếc máy ảnh của anh chỉ có thể chụp những bức ảnh có kích thước $H \times W$. Do máy chỉ có thể bay song song trục tuyến trắc từ trên mà không thể quay nên những bức ảnh sẽ có chiều dài $H$ theo hướng Bắc – Nam và $W$ theo chiều Đông – Tây.

Cũng do giới hạn kĩ thuật, nếu bức ảnh của Tuấn có nhiều hơn một nửa số người mặc áo cùng màu, bức ảnh sẽ bị cháy màu. Do đó Tuấn muốn tìm cách tiết kiệm phim cho máy của mình bằng cách chỉ chụp những bức ảnh sao cho không bị cháy.

Yêu cầu: Bạn hãy giúp Tuấn đếm số bức ảnh có thể chụp mà không bị cháy màu nhé.

**Dữ liệu**

Vào từ file văn bản GPICTURES.INP:

Dòng đầu tiên chứa hai số nguyên dương $m, n$ $(1 \le n \times m \le 10^6)$ là kích thước khán đài của sân vận động Mỹ Đình

Dòng thứ hai chứa hai số nguyên dương $H, W$ $(H \le m, W \le n)$ mô tả kích thước ảnh mà máy của Tuấn có thể chụp được

$m$ dòng sau, dòng thứ $i$ chứa $n$ số nguyên dương $a_{i,1}, a_{i,2}, \ldots, a_{i,n}$ $(a_{i,j} \le 10^9)$ mô tả các khán giả đi xem trận bóng

**Kết quả**

Xuất ra file văn bản GPICTURES.OUT:

Một số nguyên duy nhất là số bức ảnh Tuấn có thể chụp mà không bị cháy màu

**Ràng buộc**

Có $30%$ số điểm với $m \times n \le 1000$

Có $20%$ số điểm với $m = 1, n \le 10^6$

Có $30%$ số điểm với $m \times n \le 10^6$, $a_{i,j} \le 5 \ \forall\ 1 \le i \le m,\ 1 \le j \le n$

Còn lại không có điều kiện gì thêm

**Ví dụ**
Ví dụ 1

Input

2 4
1 3
1 5 4 5
4 5 7 6

Output

Giải thích

Có 3 ảnh thỏa mãn là:

[1 5 4]
[4 5 7]
[5 7 6]

Ví dụ 2

Input

4 3
1 2
3 6 3
2 4 2
6 5 1
1 2 3

Output

Giải thích

Mọi ảnh đều không bị cháy màu.

Ví dụ 3

Input

2 4
1 4
3 1 1 1
7 7 7 3

Output

Giải thích

Không có ảnh nào thỏa mãn cả.

✅ Đã AC: 0 / 1 submissions