시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 504 | 233 | 192 | 48.363% |
승원이는 미술품 N개를 가지고 있다. 각각의 미술품은 1번부터 N번까지 번호가 매겨져 있다. i번 미술품의 크기는 Ai, 가치는 Bi로 나타낸다.
오늘은 승원이의 저택 1층에서 미술품을 전시하려고 한다. 승원이는 아래 조건을 만족하는 미술품을 골라서 전시하려고 한다.
승원이가 가지고 있는 미술품 N개의 크기와 가치가 주어졌을 때, S − (Amax − Amin) 의 최댓값을 구하는 프로그램을 작성하시오.
첫째 줄에 승원이가 가지고 있는 미술품의 개수 N (2 ≤ N ≤ 500,000)이 주어진다.
둘째 줄부터 N개의 줄에 미술품의 크기 Ai와 가치 Bi가 1번 미술품 부터 순서대로 주어진다. (1 ≤ Ai ≤ 1,000,000,000,000,000 = 1015, 1 ≤ Bi ≤ 1,000,000,000)
첫째 줄에 S − (Amax − Amin) 의 최댓값을 출력한다.
번호 | 배점 | 제한 |
---|---|---|
1 | 10 | N ≤ 16. |
2 | 20 | N ≤ 300. |
3 | 20 | N ≤ 5000. |
4 | 50 | 추가적인 제약 조건이 없다. |
3 2 3 11 2 4 5
6
6 4 1 1 5 10 3 9 1 4 2 5 3
7
15 1543361732 260774320 2089759661 257198921 1555665663 389548466 4133306295 296394520 2596448427 301103944 1701413087 274491541 2347488426 912791996 2133012079 444074242 2659886224 656957044 1345396764 259870638 2671164286 233246973 2791812672 585862344 2996614635 91065315 971304780 488995617 1523452673 988137562
4232545716
예제 1의 경우에 승원이는 3개의 미술품을 가지고 있고, 크기와 가치는 다음과 같다.
이때는, 1번과 3번을 전시하면 S − (Amax − Amin) = 6가 되고, 가장 큰 값이다.
따라서, S = 8 이고, S − (Amax − Amin) 는 6이다.