Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

YUGI - Yugi-Oh

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274707/problem/S

Các bạn đã đọc bộ truyện tranh Nhật Bản Yugi-oh chắc hẳn ai cũng cực kì yêu thích trò chơi bài Magic. Bộ bài và chiến thuật chơi quyết định đến sự thắng thua của đối thủ(mà sự thắng thua thì còn liên quan đến cả tính mạng >_<). Vì thế tầm quan trọng của bộ bài là rất lớn. Một bộ bài tốt không chỉ bao gồm các quân bài mạnh mà còn phụ thuộc vào sự hỗ trợ tương tác giữa các quân bài. Bộ bài của Yugi là một bộ bài có sự bổ sung, hỗ trợ cho nhau rất tốt, điều này là 1 trong các nguyên nhân khiến Kaiba luôn là kẻ chiến bại.

Tình cờ Kaiba đã tìm được 1 quân bài ma thuật mà chức năng của nó là chia bộ bài hiện có của đối thủ ra làm K phần, mỗi phần có ít nhất 1 quân bài (điều này làm giảm sức mạnh của đối thủ). Kaiba quyết định áp dụng chiến thuật này với Yugi. Hiện tại Yugi có trong tay N quân bài, 2 quân bài i, j có sức mạnh tương tác a(i,j) (a(i,j) = a(j,i)). Kaiba muốn chia các quân bài thành K phần theo quy tắc sau:

  • Giả sử K phần là P1, P2, ..., Pk thì độ giảm sức mạnh giữa 2 phần u,v là b(u,v) = min(a(i,j) với i thuộc Pu, j thuộc Pv).
  • Độ giảm sức mạnh của bộ bài là S = min(b(u,v) với 1 ≤ u, v ≤ K).

Kaiba muốn chia K phần sao cho S lớn nhất

Input

  • Dòng đầu là 2 số N,K(2 ≤ K ≤ N ≤ 200)
  • N dòng tiếp theo mỗi dòng là N số a(i,j) (a(i,j) ≤ 32767; nếu i = j thì a(i,j) = 0)

Output

Gồm 1 dòng duy nhất là S lớn nhất

Example

Input:
4 3
0 1 2 3
1 0 2 3
2 2 0 3
3 3 3 0

Output:
2

Được gửi lên bởi:Nghia Nguyen Hoang
Ngày:2007-09-13
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Không rõ nguồn gốc

hide comments
2019-07-31 14:27:00
DSU + binary search 1 đấm AC :>>>
2018-11-22 06:01:14
BFS một đấm AC, không cần cây khung đâu.
2018-09-03 16:57:37
nhật hào sạch
2018-01-07 11:53:20
ledacthuongvq
2016-06-23 08:54:04
Kruskal 1 dấm AC :)
2015-11-15 08:16:30
THAM KHẢO TẠI https://traitaodo.wordpress.com/2015/11/15/yugi-oh-yugi/
2015-09-14 11:11:25 N�ng D�n John
http://nhatkynghiencuu.blogspot.com/2015/06/yugi-oh-ma-yugi-spoj.html
2015-06-27 11:59:06 N�ng D�n John
Đã thông và đã AC sau 4 phát
2014-09-18 06:04:36 Thcs Ðặng Chánh Kỷ
bai hay
2014-08-06 15:35:10 Phạm Trung Hiếu
dong y vs vo dai dung.
tac dung k co, vut la ay di con hon
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.