시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 1057 | 290 | 203 | 33.170% |
상근이는 도서관에서 번 돈으로 서강대 곤자가 플라자에 레스토랑을 하나 열었다. 이 레스토랑에는 음식을 N종류 팔고 있고, 손님은 서로 다른 음식을 여러개 시킬 수 있다. 이때, 음식을 시키는 순서가 중요하다. 그 이유는 각 음식을 첫 번째로 시킬 때의 가격과 아닐 때의 가격이 다르기 때문이다. 즉, 모든 음식 i의 가격은 첫 번째로 시킬 때의 가격 Ai와 아닐 때의 가격 Bi 두가지가 있다.
배가 고픈 창영이는 상근이네 레스토랑에서 음식을 시켜먹으려고 한다. 이때, 1개, 2개, ..., N개 시킬 때 필요한 최소 가격을 각각 구하는 프로그램을 작성하시오. 같은 종류 음식을 여러 번 중복해서 주문할 수 없다.
첫째 줄에 상근이네 레스토랑의 음식의 개수 N(2 ≤ N ≤ 500,000)이 주어진다. 다음 N개의 줄에는 각 음식의 가격 Ai와 Bi가 주어진다. (0 ≤ Ai, Bi ≤ 1,000,000,000)
출력은 총 N개로 이루어져 있다. i번째 줄에는 음식을 i개 시킬 때 필요한 최소 가격을 출력한다.
3 10 5 9 3 10 5
9 13 18
2 100 1 1 100
1 2
5 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1000000000 2000000000 3000000000 4000000000 5000000000
Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #2 4번