시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 2042 | 674 | 498 | 31.047% |
농부 상헌이는 선재의 부동산에서 N개의 땅을 모두 사려고 한다. 땅은 Wi * Hi 크기의 직사각형으로 생각할 수 있다.
선재는 그동안 땅 하나의 가격을 Wi * Hi로 매겨서 팔았는데, 사실 요즘 선재는 장사가 잘 안 된다. 손님이 급한 선재는 다음과 같은 묶음 할인 행사를 통해서 땅을 팔고 있다.
상헌이는 선재의 행사가 매우 좋다고 생각해서 땅을 살 준비를 하고 있었지만, 땅을 어떻게 묶어사는지에 따라 가격이 천차만별이라는 사실을 깨닫게 되었다! 상헌이가 최소 비용으로 땅을 묶어서 살 경우, 최소 비용은 얼마일까?
첫 번째 줄에 N이 주어진다. (1 <= N <= 50000)
이후 N개의 줄에 Wi, Hi가 주어진다. (1 <= Wi, Hi <= 1000000)
상헌이가 땅을 사는 최소 비용을 출력하라.
4 100 1 15 15 20 5 1 100
500
(1) / (4) / (2, 3) 으로 땅을 묶어 사보자. 상헌이는 100 * 1 + 20 * 15 + 1 * 100 = 500의 가격에 땅을 살 수 있다.
Olympiad > USA Computing Olympiad > 2007-2008 Season > USACO March 2008 Contest > Gold 1번