menu
大连理工大学 DP·AC算法竞赛协会 ICPC集训队 Online Judge
account_circle
请登录
登录
注册
home
首页
book
题目
library_books
题单
apps
分类
play_circle_outline
状态
layers
竞赛/作业
equalizer
排名
assignment_ind
登录
person_add
注册
1083: 矩阵消除游戏
时间限制:
1.000s
内存限制:
128MB
提交
通过: 1
提交: 2
统计
题目描述
牛妹在玩一个名为矩阵消除的游戏,矩阵的大小是
n{n}
n
行
m{m}
m
列,第
i{i}
i
行第
j{j}
j
列的单元格的权值为
ai,ja_{i,j}
a
i
,
j
,牛妹可以进行
k{k}
k
个回合的游戏,在每个回合,牛妹可以选择一行或者选择一列,然后将这一行或者这一列的所有单元格中的权值变为
0{0}
0
,同时牛妹的分数会加上这一行或者这一列中的所有单元格的权值的和。
牛妹想最大化她的得分,球球你帮帮她吧!
输入格式
第一行三个整数
n,m,k{n,m,k}
n
,
m
,
k
接下来
n{n}
n
行每行
m{m}
m
个整数表示矩阵中各个单元格的权值。
备注:
1
≤
n
,
m
≤
1
5
1≤ai,j≤1e61\leq a_{i,j}\leq 1e6
1
≤
a
i
,
j
≤
1
e
6
1≤k≤n∗m1\leq k\leq n*m
1
≤
k
≤
n
∗
m
输出格式
输出一个整数表示牛妹能获得的最大分数。
样例输入
content_copy
3 3 2 101 1 102 1 202 1 100 8 100
样例输出
content_copy
414
分类
贪心 枚举
提交