TLE-oj Cup Round 7 - Hình chữ nhật

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

Thời gian: 1.0s

Bộ nhớ: 256M

Input: RECTS.inp

Output: RECTS.out

Tác giả:

Sunlight

Dạng bài

Cho một bảng hình chữ nhật có kích thước $m \times n$ ( $m$ hàng $n$ cột) và hai dãy số nguyên $a_1, a_2, ..., a_m$ và $b_1, b_2, ..., b_n$ . Ô ở hàng $i$ cột $j$ của bảng sẽ được điền số $a_i + b_j$ . Bạn phải cắt ra $k$ hình chữ nhật, mỗi hình chữ nhật có kích thước là $h \times w$ ( $h$ hàng $w$ cột, không được xoay), và các hình chữ nhật không được có ô chung (có thể chung đỉnh hoặc chung cạnh), sao cho tổng các số được ghi trên các ô của các hình chữ nhật là lớn nhất.

Input, Output và Subtasks

Input: (RECTS.inp)

Dòng đầu tiên gồm $5$ số nguyên dương: $m, n, h, w, k$ . Dữ liệu đầu vào đảm bảo $m \ge k \times h$ và $n \ge k \times w$ .
Dòng thứ hai gồm $m$ số nguyên không âm $a_1, a_2, ..., a_m$ $(0 \le a_i \le 10^8)$ .
Dòng thứ ba gồm $n$ số nguyên không âm $b_1, b_2, ..., b_n$ $(0 \le b_i \le 10^8)$ .

Output: (RECTS.out)

In ra tổng các số lớn nhất có thể đạt được.

Subtasks

	$m, n \le 10$ , $h = w = 1$	$m, n \le 10$	$m, n \le 100$	$m, n \le 10^5$	Tổng
$k = 1$	$3\%$	$6\%$	$9\%$	$12\%$	$30\%$
$k = 2$	$3\%$	$6\%$	$9\%$	$12\%$	$30\%$
$k = 3$	$4\%$	$8\%$	$12\%$	$16\%$	$40\%$
Tổng	$10\%$	$20\%$	$30\%$	$40\%$	$100\%$

Sample 1

Input (RECTS.inp)

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

Output (RECTS.out)

Note

	Cột $1$ $(1)$	Cột $2$ $(1)$	Cột $3$ $(1)$	Cột $4$ $(1)$
Hàng $1$ $(1)$	$2$	$2$	$2$	$2$
Hàng $2$ $(1)$	$2$	$2$	$2$	$2$
Hàng $3$ $(2)$	$3$	$3$	$3$	$3$

Một trong những cách chọn tốt nhất là chọn các ô $(2, 1), (2, 2)$ , $(3, 1)$ , $(3, 2)$ tạo thành hình vuông $2 \times 2$ có tổng giá trị là $10$ .

Sample 2

Input (RECTS.inp)

4 4 2 2 2
1 3 2 0
1 1 1 1

Output (RECTS.out)

Note

	Cột $1$ $(1)$	Cột $2$ $(1)$	Cột $3$ $(1)$	Cột $4$ $(1)$
Hàng $1$ $(1)$	$2$	$2$	$2$	$2$
Hàng $2$ $(3)$	$4$	$4$	$4$	$4$
Hàng $3$ $(2)$	$3$	$3$	$3$	$3$
Hàng $3$ $(0)$	$1$	$1$	$1$	$1$

Cách chọn tối ưu là cách chọn hai hình chữ nhật:

Hình chữ nhật thứ nhất có góc trái trên $(2, 1)$ và góc phải dưới $(3, 2)$ .
Hình chữ nhật thứ nhất có góc trái trên $(2, 3)$ và góc phải dưới $(3, 4)$ .

Tổng giá trị của hai hình chữ nhật này là $28$ .

Sample 3

Input (RECTS.inp)

6 6 2 2 3
1 3 2 0 0 0
1 2 3 1 2 2

Output (RECTS.out)

Note

Cách chọn tối ưu là cách chọn ba hình chữ nhật:

Hình chữ nhật thứ nhất có góc trái trên $(1, 2)$ và góc phải dưới $(2, 3)$ .
Hình chữ nhật thứ nhất có góc trái trên $(3, 2)$ và góc phải dưới $(4, 3)$ .
Hình chữ nhật thứ nhất có góc trái trên $(5, 2)$ và góc phải dưới $(6, 3)$ .

Tổng giá trị của hai hình chữ nhật này là $52$ .

Bình luận

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