#B3781. [语言月赛202306] 信

    ID: 330 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>模拟2023O2优化循环结构语言月赛

[语言月赛202306] 信

题目描述

信是具有重量的。信封有重量,信纸也有重量。由于信封和信纸都很薄,我们认为每平方厘米信封的重量为 xx 毫克,每平方厘米信纸的重量为 yy 毫克。 此外,有的信封中还会有一些礼物,这些礼物一定有重量。

zyl 收到了 nn 封信,他能精确测量出每封信中信封的面积 SS(单位:平方厘米)、信纸的面积 ss(单位:平方厘米)以及整封信的重量 MM(单位:毫克),保证这三个数据都是整数。在拆开信件的过程中,他会按照如下规则积累惊喜值(初始时惊喜值为 00):

  • 如果信封没有任何礼物(即信封中礼物重量为 00),他的惊喜值不变。但是,如果连续 bb 封及以上的信里都没有礼物,则从第 bb 封信开始,每拆开一封没有礼物的信,zyl 的惊喜值都会减半,然后向下取整,直到拆开一封有礼物的信。如果惊喜值原本即为 00,则不会变化。
  • 如果信封里有礼物,设礼物的质量为 MM' 毫克,则 zyl 的惊喜值会增加 MM'。如果礼物的质量大于信封和信纸的总质量,则会额外增加 0.5 M0.5\ M',然后向上取整。如果连续 aa 封及以上的信里有礼物,则从第 aa 封信开始,每拆开一封有礼物的信,zyl 的惊喜值都会在计算完这次本身的加成后再乘 22,直至拆开一封没有礼物的信。

现在按照 zyl 拆信的顺序给出 nn 封信的信息,请你求出 zyl 在拆信过程中最高的惊喜值和最终的惊喜值。

输入格式

输入共 n+1n+1 行。

第一行五个整数 n,x,y,a,bn,x,y,a,b,含义如题所示。
接下来 nn 行,每行三个整数 S,s,MS,s,M。表示这封信的信封面积,信纸面积和总质量,单位分别为平方厘米 、平方厘米、毫克。

输出格式

输出共一行两个整数,第一个表示拆信过程中的最高惊喜值,第二个表示最终的惊喜值,二者之间使用空格隔开。

6 1 1 2 2
5 3 10
6 2 12
2 3 5
2 3 11
3 5 8
2 2 4
21 10

提示

样例 1 解释

惊喜值的变化如下表: | 信的序号 | 礼物重量 | 惊喜值增加 | 额外增加 | 是否折半 | 是否翻倍 | 惊喜值 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | 1 | 22 | 22 | 00 | 否 | 否 | 22 | | 2 | 44 | 44 | 00 | 否 | 是 | 1212 | | 3 | 00 | 00 | 00 | 否 | 否 | 1212 | | 4 | 66 | 66 | 33 | 否 | 否 | 2121 | | 5 | 00 | 00 | 00 | 否 | 否 | 2121 | | 6 | 00 | 00 | 00 | 是 | 否 | 1010 |

最高的惊喜值为 2121,最终的惊喜值为 1010

数据规模与约定

对于 40%40\% 的数据,n1000n\leq 1000,任意时刻的惊喜值不会超过 10910^{9}
对于另外 20%20\% 的数据,a=b=na=b=n
对于 100%100\% 的数据,1a,bn1061\leq a,b\leq n\leq 10^{6}1x,y201\leq x,y\leq 201S,s5001\leq S,s\leq 500x×S+y×sM105x\times S+y\times s\leq M\leq 10^{5},任意时刻的惊喜值不会超过 101810^{18}