시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 434 | 120 | 94 | 30.225% |
동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 인간들이 자주 즐겨먹는 과자인 “프링글스”를 발견하게 되었다. 그리고 그 원숭이는 결국 뚜껑을 열어버렸다.ㅠㅠ 불쌍한 원숭이. 이제 그는 절대 멈출 수 없다.
원숭이가 새로운 맛의 프링글스를 먹을 때 마다 원숭이는 중독스트레스를 스스로 조절한다. 그런데 각 맛마다 중독스트레스를 조절할 수 있는 범위가 정해져 있어서 그 범위 내에서만 조절이 가능하다.
그런데 원숭이는 참 슬프게도 중독스트레스를 조절할 때 마다 예상수명이 1년씩 줄어든다. 예를 들어서 중독스트레스의 값이 5였는데 그것을 3이나 7로 조절하였다면 예상수명이 2년이나 줄어들게 되는 것이다.ㅠㅠ
원숭이는 N개의 서로 다른 맛의 프링글스 뚜껑을 모두 열어버렸으므로 이제 멈출 수 없다. N개의 서로 다른 맛의 프링글스를 순서대로 먹어야 한다. 프링글스를 하나도 먹지 않았을 때는 중독스트레스의 값을 원숭이 마음대로 조절할 수 있다. 프링글스를 한통씩 먹으면서 원숭이가 중독스트레스를 조절하는데 그때 예상수명이 줄어드는 것을 최소화하는 프로그램을 작성하시오.
첫째 줄에 프링글스 맛의 개수 N이 주어진다. N은 1이상 100,000이하인 정수이다. 그 다음 줄부터 N줄에 걸쳐 두 개의 정수 si, ei (1 ≤ si ≤ ei ≤ 200)가 주어지는데, i번째 프링글스 맛의 중독스트레스 조절범위가 si이상 ei이하라는 뜻이다. 프링글스를 먹을 때에는 입력에서 주어진 순서대로 먹어야 한다.
첫째 줄에 원숭이의 줄어든 예상수명의 양의 최솟값을 출력한다. 그 다음 줄부터 N줄에 걸쳐 각 프링글스를 먹을 때 조절한 중독 스트레스의 값을 출력하시오.
5 1 5 16 25 3 7 1 100 37 49
50 5 16 7 7 37