比赛场次 230
比赛名称 20140414
比赛状态 已结束比赛成绩
开始时间 2014-04-14 08:00:00
结束时间 2014-04-14 11:30:00
开放分组 全部用户
注释介绍 usaco 2014 2月月赛金组题
题目名称 奶牛的十项全能
输入输出 deca.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatarcstdio AAAAAAAAAA 0.693 s 4.32 MiB 100
Gravatardigital-T AAWAAAAAAA 1.212 s 4.32 MiB 90
GravatarLuciFer_T-J AAAWWWWWWW 3.024 s 0.32 MiB 30
Gravatar◆半城烟沙灬為你打天下 AAATTTTTTT 7.001 s 0.32 MiB 30
GravatarSuke AAATTTTTTT 7.001 s 0.32 MiB 30
Gravatarzgyzhaoguangyang AAATTTTTTT 7.004 s 0.17 MiB 30
Gravatar(ˇˍˇ) ~耶稣 AAATTTTTTT 7.006 s 0.32 MiB 30
GravatarHZOI_lhy111 AAWWWWWWWW 0.004 s 0.32 MiB 20
Gravatar隨風巽 AWWWWWWWWW 0.003 s 0.31 MiB 10
GravatarMiku_lyt WAWWWWWWWW 0.003 s 0.51 MiB 10
GravatarFF_Sky||幻 AWWWWWWWWW 0.005 s 0.29 MiB 10
Gravatarhzoi_zyl AWWWWWWWWW 0.008 s 0.17 MiB 10

奶牛的十项全能

★★★   输入文件:deca.in   输出文件:deca.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

农夫约翰的奶牛(1≤n≤20),总是方便的标记为1……N,或许应该叫N项全能,因为有N个不同的事件(通常有10个事件)。

牛i有一个s_ij的技能水平(1<=s_ij<=1000),是牛i在参与项目j时会得到的分数。每头奶牛必须且只能参加一个项目,每个事件必须有一些牛参加。

所有奶牛总得分为他们参加项目事件中的技能水平和。然而,项目的裁判如果有深刻印象,可以给出奖励分。评委可以给出B种奖励分(1≤B≤20)。奖励分i有三部分:如果奶牛在前k_i事件(包括这些事件其他牛的分数)获得了至少p_i(1< = p_i<=40000)分,他们将获得额外的a_i(1<=a_i<=1000)分(前k项触发的奖励积分不算到前k项的分数和,但算到之后的分数和中)。

例如,让我们考虑n = 3头牛技能水平如下:

  cow
event   1 2 3
1 5 1 7
2 2 2 4
3 4 2 1

【输入格式】

第1行为N和B;

接下来有B行(2--B+1),其中第i+1行为 K_i, P_i,A_i;

再接下来有N行(B+2--B+1+N),其中第B+N+j行表示 s_j1...s_jN. 。

【输出格式】

输出只有一行,即牛得到的最大分数,包括奖励分。

【样例输入】

3 1
2 7 6
5 1 7
2 2 4
4 2 1

【样例输出】

17

【提示】

输出解释:

牛1参与项目1,牛2参与项目3,牛3参与项目2。

【来源】

USACO Feb14