传统题 文件IO:grid 2000ms 512MiB

grid

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

grid

题目描述

给出一张 n×nn \times n 的网格,每个点有权值 ai,ja_{i,j} (坐标下标从 1n1\sim n )

现在你需要选取mm个点出来,一个选出的点被认为是好点当且仅当 i=1i=1 oror (i1,j1)(i-1,j-1)(i1,j+1) (1<j<n)(i-1,j+1) \ (1 <j <n) 这两个点都被选了 (若这两个点其中之一不在网格上,那么不符合条件),否则是一个坏点

一种合法的选点方案当且仅当坏点个数小于等于kk

求对于 m=1n2m=1 \sim n^2 ,选出的点权值和最大分别是多少

若不存在合法方案,输出 1-1

输入格式

第一行两个整数 n,kn,k

接下来 nn 行每行 nn 个整数,第 ii 行第 jj 个数代表 ai,ja_{i,j}

输出格式

输出 n2n^2 行第 ii 行代表 m=im=i 时的答案。

样例
样例输入 #1
2 0
2 3
4 5
样例输出 #1
3
5
-1
-1
样例输入 #2
2 1
2 3
4 5
样例输出 #2
5
8
10
-1
样例输入 #3
4 0
2 1 0 8 
0 10 1 0
0 0 0 0
0 0 0 0
样例输出 #3
8
10
12
20
21
22
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
样例输入 #4
5 1
5 0 5 0 0 
0 140 0 10 0
0 0 150 0 0
0 0 0 0 0
0 0 0 0 0
样例输出 #4
150
155
160
300
310
310
310
310
310
310
310
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
数据范围与限制

对于所有数据,保证

$2\leq n\leq 140, \ k\leq 1, \ 0\le a_{i,j} \le 10^9$

任务编号 任务分数 特殊限制
11 1010 n4, k=0n\le 4, \ k=0
22 2020 n9, k=0n\le 9, \ k=0
33 k=0k=0
44 30 30 n50n\le 50
55 2020 无特殊限制

注意本题采用捆绑测试

BOC云冲刺 Round2 镜像赛

未参加
状态
已结束
规则
OI
题目
4
开始于
2023-11-9 18:00
结束于
2023-11-9 22:30
持续时间
4.5 小时
主持人
参赛人数
2