레이팅 미적용골디락스에게는 N마리 (1 <= N <= 20,000)의 소가 있는 헛간이 있다. 골디락스의 소들은 온도에 꽤 민감하다.
각 소 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 범위의 정수이며, 온도 조절기는 임의의 정수 값으로 설정할 수 있다.
첫째 줄: 공백으로 구분된 네 정수 N X Y Z.
둘째 줄부터 1+N번째 줄까지: 1+i번째 줄에 공백으로 구분된 두 정수 A(i)와 B(i)가 주어진다.
골디락스가 헛간의 온도를 최적으로 설정하여 얻을 수 있는 우유의 최대량.
milktemp.in · 출력을 쓸 파일 milktemp.out4 7 9 6
5 8
3 4
13 20
7 1031Output details: Setting the thermostat to 7 or 8 makes cows #1 and #4 happy (cow #2 too hot, cow #3 too cold), yielding 31 units of total milk.
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > November > Bronze