TLE-oj Cup Round 1 - Treo tranh - TLEOJ: TLE Online Judge

TLE-oj Cup Round 1 - Treo tranh

Điểm: 2000 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 512M

Input: PICTURE.inp

Output: PICTURE.out

Tác giả:

aisukiuwu

Dạng bài

Vào một ngày đẹp trời, mèo mẹ mang về cho mèo con $p$ bức tranh $1\times2$ và $q$ bức tranh $2\times1$ . Những con mèo con rất thích bức tranh này và chúng quyết định treo hết bức tranh lên tường. Bức tường của nhà mèo có thể biểu diễn dạng một lưới ô vuông $m \times n$ và nếu treo 1 bức tranh có kích thước $a \times b$ thì bức tranh sẽ chiếm $a \times b$ ô trên lưới. Những bức tranh không được phép treo đè lên nhau. Mèo mẹ viết lên ô $(i, j)$ một số nguyên không âm $a_{i, j}$ $(\left| a_{i, j} \right| \le 10^3)$ và đố những con mèo con treo như thế nào để có tổng giá trị $C$ lớn nhất. Giá trị $C$ được tính như sau:

Với bức tranh $1 \times 2$ : (có thể lấy hình ở đây)

Với bức tranh $2 \times 1$ : (có thể lấy hình ở đây)

Những con mèo con đã ngồi tìm hàng giờ mà vẫn chưa tìm được kết quả. Vì vậy chúng đã nhờ bạn giúp và nếu bạn giúp được bạn sẽ nhận được $1$ con cá :Đ

Test luôn thỏa mãn yêu cầu của đề bài, nghĩa là luôn có cách treo $p$ bức tranh $1\times2$ và $q$ bức tranh $2\times1$ lên bức tường $m \times n$ .

Input, Output và Subtasks

Input: (PICTURE.inp)

Dòng đầu tiên gồm số nguyên dương $m, n, p, q$ $(1 \le m \le 10,1 \le n \le 10,0 \le p \le 10, 0\le q\le 10)$ lần lượt là độ dài $2$ cạnh của tường, số bức tranh $1\times2$ và số bức tranh $2\times1$ .
$m$ dòng tiếp theo, mỗi dòng gồm $n$ số nguyên $(\left| a_{i, j} \right| \le 10^3)$ .

Output: (PICTURE.out)

Kết quả là $1$ số nguyên $C$ duy nhất.

Subtasks

$10$ % số điểm có $m \le 3, n \le 3$ .
$30$ % số điểm có $p \le 1, q \le 1$ .
$60$ % còn lại không giới hạn gì thêm.

Sample

Input (PICTURE.inp)

Output (PICTURE.OUT)

Notes

Những con mèo có thể treo tranh $1 \times 2$ ở vị trí $(a_{1, 2}, a_{2, 2})$ và treo tranh $2 \times 1$ ở vị trí $(a_{2, 3}, a_{3, 3})$ . Vậy $C=(3-1)+(2+1)=5$ .

Bình luận

Không có bình luận nào.