#C. CSP-模拟赛005-T3

    传统题 1000ms 256MiB

CSP-模拟赛005-T3

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

题目描述

猪猪侠吃了超级棒棒糖之后,获得了一种能力,它能够知道未来 TTNN 种超级棒棒糖每天的价格。某个超级棒棒糖的价格是指购买一个该超级棒棒糖所需的金币数量,以及卖出一个该超级棒棒糖换回的金币数量。

每天,猪猪侠可以进行以下两种交易无限次

  1. 任选一个超级棒棒糖,若手上有足够金币,以当日价格购买该超级棒棒糖;
  2. 卖出持有的任意一个超级棒棒糖,以当日价格换回金币。

每天卖出超级棒棒糖换回的金币可以立即用于购买超级棒棒糖,当日购买的超级棒棒糖也可以当日卖出换回金币。当然,一直持有超级棒棒糖也是可以的。

TT 天之后,猪猪侠的超能力消失。因此他一定会在第 TT 天卖出所有超级棒棒糖换回金币。

猪猪侠现在有 MM 枚金币,他想要在超能力消失后拥有尽可能多的金币。

输入格式

第一行包含三个正整数 T,N,MT, N, M,相邻两数之间以一个空格分开,分别代表未来天数 TT,超级棒棒糖数量 NN,猪猪侠现在拥有的金币数量 MM

接下来 TT 行,每行包含 NN 个正整数,相邻两数之间以一个空格分隔。第 ii 行的 NN 个正整数分别为 Pi,1,Pi,2,,Pi,NP_{i,1},P_{i,2},\dots,P_{i,N},其中 Pi,jP_{i,j} 表示第 ii 天第 jj 种超级棒棒糖的价格。

输出格式

输出仅一行,包含一个正整数,表示猪猪侠在超能力消失后最多能拥有的金币数量。

样例 #1

样例输入 #1

6 1 100
50
20
25
20
25
50

样例输出 #1

305

样例 #2

样例输入 #2

3 3 100
10 20 15
15 17 13
15 25 16

样例输出 #2

217

提示

样例 1 说明

最佳策略是:

第二天花光所有 100100 枚金币买入 55 个超级棒棒糖 11

第三天卖出 55 个超级棒棒糖 11,获得金币 125125 枚;

第四天买入 66 个超级棒棒糖 11,剩余 55 枚金币;

第六天必须卖出所有超级棒棒糖换回 300300 枚金币,第四天剩余 55 枚金币,共 305305 枚金币。

超能力消失后,猪猪侠最多拥有 305305 枚金币。

样例 2 说明

最佳策略是:

第一天花光所有金币买入 1010 个超级棒棒糖 11

第二天卖出全部超级棒棒糖 11 得到 150150 枚金币并买入 88 个超级棒棒糖 2211 个超级棒棒糖 33,剩余 11 枚金币;

第三天必须卖出所有超级棒棒糖换回 216216 枚金币,第二天剩余 11 枚金币,共 217217 枚金币。

超能力消失后,猪猪侠最多拥有 217217 枚金币。

数据规模与约定

对于 10%10\% 的数据,T=1T = 1

对于 30%30\% 的数据,T4,N4,M100T \leq 4, N \leq 4, M \leq 100,所有价格 10Pi,j10010 \leq P_{i,j} \leq 100

另有 15%15\% 的数据,T100,N=1T \leq 100, N = 1

另有 15%15\% 的数据,T=2,N100T = 2, N \leq 100

对于 100%100\% 的数据,T100,N100,M103T \leq 100, N \leq 100, M \leq 10^3,所有价格 1Pi,j1041 \leq P_{i,j} \leq 10^4,数据保证任意时刻,猪猪侠手上的金币数不可能超过 10410^4

2024 CPS第二轮-模拟赛第四天

未参加
状态
已结束
规则
OI
题目
5
开始于
2024-10-4 9:00
结束于
2024-10-4 13:00
持续时间
4 小时
主持人
参赛人数
19