DOMINO8  DOMINO
Mirko received an N × N table for his birthday, where a nonnegative integer is written in each field
of the table. Unfortunately, the written numbers are too large for Mirko’s taste, so he will place K
dominoes on top of the table that will cover the fields that are too large.
More precisely, Mirko places the dominoes according to the following rules:
• each domino covers two fields of the table that are adjacent in a row or in a column,
• the dominoes do not overlap (but can touch),
• the sum of all visible (uncovered) fields needs to be as small as possible.
It is your task to determine the required minimal sum of visible fields. The test data will be such that
it will always be possible to place K dominoes without overlapping..
Input
The first line of input contains the integers N (1 <= N <= 2000), the dimensions of the table, and K
(1 <= K <= 8), the number of dominoes. Each of the following N lines contains N integers from
the interval [0, 1000]. These N × N numbers describe Mirko’s table
Output
The first and only line of output must contain the minimal sum of visible fields after covering the
table with dominoes.
Example
Input: 3 1
2 7 6
9 5 1
4 3 8 Output: 31
Input:
4 2
1 2 4 0
4 0 5 4
0 3 5 1
1 0 4 1
Output:
17
Clarification of the first example: We place the domino so it covers fields with numbers 9 and 5.
Clarification of the second example: We place the dominoes so they cover fields [4, 5] and [5, 4] in the third column.
hide comments
๖ۣۜDark๖ۣۜStar:
20151205 09:08:21
Nguyen Thanh Tung is "Suu Nhi" 

Nguyễn Thanh Tùng:
20151205 09:05:26
cạp cạp Last edit: 20151205 09:09:06 

Nguyễn Thanh Tùng:
20151205 09:04:58
Last edit: 20151205 09:06:55 

Nguyễn Thanh Tùng:
20151205 09:01:38
Last edit: 20151205 09:06:43 
Added by:  Gầy :)) 
Date:  20151130 
Time limit:  1s5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  COCI 2015 Round 3 