网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[USACO NOV]金发姑娘和N头牛
成绩 | 开启时间 | 2014年09月19日 星期五 10:07 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:07 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:07 |
输入文件 | milktemp.in | 输出文件 | milktemp.out |
【题目描述】
你可能已经听说了金发姑娘和3只熊的经典故事。
鲜为人知的是,金发姑娘最终经营了一个农场。在她的农场,她有一个谷仓含N头奶牛(1<=N <= 20000)。不幸的是,她的奶牛对温度相当敏感。
第i头奶牛必须在指定的温度范围内A(i)..B(i)才感觉舒适;(0<=A(i)<=B(i)<= 1,000,000,000)。如果金发姑娘在谷仓放置一个温控器;如果温度T<A(i),牛会太冷,并将产生x单位牛奶。如果她把恒温器调到(A(i)<=T<=B(i))这个范围内,那么牛会感到舒适,并将产生Y单位牛奶。如果她把恒温器调到温度T>B(i),牛会感觉很热,并将产生的Z单位牛奶。正如预期的那样,Y的值总是大于X和Z。
给定的X,Y,和Z,以及每个牛的温度的最佳范围,如果金发姑娘设置谷仓的温控器最佳,请计算金发姑娘得到牛奶的最大数量,已知X,Y和Z都是整数,范围0..1000。温控器可以设置为任意整数的值。
【输入格式】
第1行:四个用空格隔开的整数:N X Y Z。
第2行..1 + N:行1+i包含两个用空格隔开的整数:A(i)和B(i)。
【输出格式】
1行:金发姑娘最多可以获得的牛奶,当她在谷仓的最佳温度设定。
【样例输入】
4 7 9 6 5 8 3 4 13 20 7 10
【样例输出】
31
【提示】
在农场里有4头奶牛,温度范围5..8,3..4,13..20,10..7。一个寒冷的奶牛生产7单位的牛奶,一个舒适的奶牛生产9个单位的牛奶,一个热牛生产6单位牛奶。
【数据规模】
50%的测试数据:n<=5
其余50%的测试数据:10000<n<=20000.
【来源】
USACO 2013 November Contest, Bronze
translate by cqw
data from cstdio