2786번 - 상근이의 레스토랑 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 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개 시킬 때 필요한 최소 가격을 출력한다.
예제 입력 1
3 10 5 9 3 10 5
예제 출력 1
9 13 18
- 음식을 1개 시킬 때는, 2번을 시키면 된다. (9)
- 음식을 2개 시킬 때는, 1번을 시키고, 2번을 시키면 된다. (10+3)
- 음식을 3개 시킬 때는, 1번을 시키고, 2번, 3번을 시키면 된다. (10+3+5)
예제 입력 2
2 100 1 1 100
예제 출력 2
1 2
예제 입력 3
5 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
예제 출력 3
1000000000 2000000000 3000000000 4000000000 5000000000
출처
Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #2 4번
- 빠진 조건을 찾은 사람: adfsfsf
- 문제를 번역한 사람: arine, baekjoon
- 잘못된 조건을 찾은 사람: surung9898
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호