#P5322. [BJOI2019] 排兵布阵

    ID: 198 远端评测题 1000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划,dp2019各省省选北京O2优化背包

[BJOI2019] 排兵布阵

题目描述

小 C 正在玩一款排兵布阵的游戏。在游戏中有 nn 座城堡,每局对战由两名玩家来争夺这些城堡。每名玩家有 mm 名士兵,可以向第 ii 座城堡派遣 aia_i 名士兵去争夺这个城堡,使得总士兵数不超过 mm

如果一名玩家向第 ii 座城堡派遣的士兵数严格大于对手派遣士兵数的两倍,那么这名玩家就占领了这座城堡,获得 ii 分。

现在小 C 即将和其他 ss 名玩家两两对战,这 ss 场对决的派遣士兵方案必须相同。小 C 通过某些途径得知了其他 ss 名玩家即将使用的策略,他想知道他应该使用什么策略来最大化自己的总分。

由于答案可能不唯一,你只需要输出小 C 总分的最大值。

输入格式

输入第一行包含三个正整数 s,n,ms,n,m,分别表示除了小 C 以外的玩家人数、城堡数和每名玩家拥有的士兵数。
接下来 ss 行,每行 nn 个非负整数,表示一名玩家的策略,其中第 ii 个数 aia_i 表示这名玩家向第 ii 座城堡派遣的士兵数。

输出格式

输出一行一个非负整数,表示小 C 获得的最大得分。

1 3 10
2 2 6
3
2 3 10
2 2 6
0 0 0
8

提示

样例1解释:
小 C 的最佳策略为向第 11 座城堡和第 22 座城堡各派遣 55 名士兵。

样例2解释:
小 C 的最佳策略之一为向第 11 座城堡派遣 22 名士兵,向第 22 座城堡派遣 55 名士兵,向第 33 座城堡派遣 11 名士兵。

数据范围:
对于 10%10\% 的数据: s=1,n3,m10s=1,n \le 3,m \le 10
对于 20%20\% 的数据: s=1,n10,m100s=1,n \le 10,m \le 100
对于 40%40\% 的数据: n10,m100n\le 10,m\le 100
对于另外 20%20\% 的数据: s=1s=1
对于 100%100\% 的数据:
1s1001\le s \le 100
1n1001\le n \le 100
1m200001\le m \le 20000
对于每名玩家 ai0a_i \ge 0i=1naim\sum\limits_{i=1}^n a_i \le m