Xây dựng đội bóng

Điểm: 8,00 (OI)

Giới hạn thời gian: 3.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Java

Có $n$ người ứng tuyển vào một câu lạc bộ thể thao. Câu lạc bộ cần chọn đúng $p$ cầu thủ thi đấu tại $p$ vị trí khác nhau (mỗi vị trí đúng một người) và đúng $k$ cổ động viên. Mỗi người chỉ có thể đảm nhận tối đa một vai trò (hoặc cầu thủ tại một vị trí, hoặc cổ động viên).

Với người thứ $i$ :

$a_{i}$ là sức mạnh người đó đóng góp nếu được chọn làm cổ động viên.
$s_{i, j}$ là sức mạnh người đó đóng góp nếu được chọn làm cầu thủ thi đấu tại vị trí $j$ .

Tổng sức mạnh của câu lạc bộ là tổng tất cả các đóng góp của những người được chọn. Hãy chọn $p$ cầu thủ (một người cho mỗi vị trí) và $k$ cổ động viên sao cho tổng sức mạnh này lớn nhất.

Dữ liệu vào

Dòng đầu chứa ba số nguyên $n$ , $p$ , $k$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .
Trong $n$ dòng tiếp theo, dòng thứ $i$ chứa $p$ số nguyên $s_{i, 1}, s_{i, 2}, \dots, s_{i, p}$ .

Dữ liệu ra

Một số nguyên duy nhất là tổng sức mạnh lớn nhất có thể của câu lạc bộ.

Ràng buộc

$2 \leq n \leq 10^{5}$
$1 \leq p \leq 7$
$1 \leq k$ và $p + k \leq n$
$1 \leq a_{i} \leq 10^{9}$
$1 \leq s_{i, j} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 1 2 1 16 10 3 18 19 13 15	44	Chọn người 1 làm cầu thủ ( $s_{1, 1} = 18$ ), người 2 và 3 làm cổ động viên ( $a_{2} + a_{3} = 16 + 10$ ). Tổng $= 18 + 26 = 44$ .
3 2 1 500 498 564 100002 3 422332 2 232323 1	422899	Người 2 làm cầu thủ vị trí 1 ( $422332$ ), người 1 làm cầu thủ vị trí 2 ( $3$ ), người 3 làm cổ động viên ( $564$ ). Tổng $= 422332 + 3 + 564 = 422899$ .
6 2 3 78 93 9 17 13 78 80 97 30 52 26 17 56 68 60 36 84 55	377	Một cách chọn tối ưu cho tổng $377$ .

Bình luận

Không có bình luận tại thời điểm này.