Chia đồng cỏ

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một lưới $N \times N$ biểu diễn số bò trong mỗi ô. Bạn có thể dựng tối đa $K$ hàng rào, mỗi hàng rào là một đường thẳng đứng hoặc nằm ngang trải qua toàn bộ chiều ngang/dọc của lưới (không được cắt xuyên qua ô). Các hàng rào chia lưới thành nhiều khu vực hình chữ nhật.

Hãy chọn cách đặt tối đa $K$ hàng rào sao cho khu vực lớn nhất (tổng số bò trong khu vực) là nhỏ nhất có thể.

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $K$
Dòng $i + 1$ (với $1 \leq i \leq N$ ): $N$ số nguyên — số bò trong mỗi ô của hàng $i$

Dữ liệu ra

Một số nguyên duy nhất: giá trị nhỏ nhất của khu vực lớn nhất

Ràng buộc

$2 \leq N \leq 15$
$1 \leq K \leq 2 N - 2$
$0 \leq$ số bò trong mỗi ô $\leq 1000$

Ví dụ

Input	Output	Giải thích
3 2 1 1 2 1 1 2 2 2 4	4	Dùng 2 hàng rào: 1 hàng ngang (sau hàng 2) và 1 hàng dọc (sau cột 2). Khu vực lớn nhất là 4 (góc dưới phải).

Bình luận

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