#P5245. 「2019-05-06提高模拟赛」经商(business)
「2019-05-06提高模拟赛」经商(business)
Description
西二百里,曰林山。政水出焉,而东流注于宇泽。有谷焉,曰洛,队爷自是出。其阴不毛,积年荒芜,少有人在彼处。其阳多金玉,一国生焉,曰 Y 国。
Y 国国主者,YC 也。YC 者,相貌昳立而衣冠堂堂也。自幼即嗜学,上知天文,下晓地理,性情淑均。自其官以来,勤政爱民,招贤纳士,劝兴商,开凿石,兴水利,除诸弊。终国富民强,振兴一方。 ——『小荒内经』
Y 国位于一条狭长的山谷中,这里虽然地理条件险恶,自然环境十分不优越,自古以来这里都是荒芜之地,可是在新任 Y 国国主 <font color"black">C</font>hangyu 的治理下,人民生活显著改善,综合国力显著增强,国际地位显著提高,全面向小康社会迈进,为 Y 国发展富强、人民生活富裕奠定了坚实基础。
尽管由于自然环境原因,Y 国在许多方面不如其它国家,但 <font color"black">C</font>hangyu 发现 Y 国富含矿产资源并进行开凿挖掘,从此 Y 国日渐富有,百姓也逐渐解决了温饱问题。
<font color"black">C</font>hangyu 又鼓励人们从事商业,在国主 <font color"black">C</font>hangyu 的鼓励下,许多人从事商业,所以近年来 Y 国的商业发展十分迅速,有的人将 Y 国廉价的矿物高价卖往其它国家,带来了巨额利益;有的人从其它国家进口生活用品到 Y 国,使得人民的生活水平显著提高,而有的人则在国内通过不同物品在不同城市间的差价谋求利益,他们往往需要根据随时变化的市场价格调整他们的经商方案。
XieRujian 就是 Y 国的一个商人,而他选择在国内经商,由于 Y 国处于峡谷之中,所以 Y 国的城市排成了一列,这也导致 Y 国的两端相距太远而且交通不十分便利,所以 XieRujian 只会在某个范围内进行经商,每次经商,他会选择一件物品,并找到他的活动范围内该物品市面价格差最大的两个城市,从低价的城市买并卖到高价的城市。当然,如果他的活动范围内该物品的价格都一样,不存在额差,那么 XieRujian 就只能 利润空手而归了。
Y 国国主 <font color"black">C</font>hangyu 调查了 XieRujian 最近 次的经商活动,得到了 XieRujian 的每一次经商活动中物品的单件利润以及所经商的物品当时在所有城市的市面价值,他想知道 XieRujian 有多少种满足的活动范围。
Input Format
输入文件名为 business.in
。
输入数据第一行两个正整数 ,表示 Y 国城市数量以及 <font color"black">C</font>hangyu 调查的经商活动数量。
接下来一行 个自然数,第 个数表示调查的第 次经商活动物品的单件利润。
接下来 行,每行 个正整数,第 行第 列正整数表示第 次经商活动的物品在第 个城市中的市面价值。
Output Format
输出文件名为 business.out
。
输出一行一个自然数,表示 XieRujian 可能的活动范围数量。
Sample
样例输入 1
5 1
2
2 3 1 4 5
样例输出 1
2
样例解释 1
满足条件的活动范围有 和 ,XieRujian 在这个活动范围内会从第三座城市买来物品,卖到第二座城市去,单个物品利润为 。
样例 2
见附加文件中的 business2.in
与 business2.ans
.
Hint
测试点编号 | 特殊性质 | ||
---|---|---|---|
无特殊性质 | |||
对于每个序列,市面价值严格单调上升 | |||
对于每个序列,市面价值单调上升 | |||
对于每个序列,市面价值不超过 种 | |||
保证单件物品利润为 | |||
无特殊性质 | |||
对于每个序列,市面价值严格单调上升 | |||
对于每个序列,市面价值单调上升 | |||
对于每个序列,市面价值不超过 种 | |||
保证单件物品利润为 | |||
无特殊性质 | |||
对于所有数据,市面价值与利润均不超过 。