레이팅 미적용설명
展示される美術品の候補の個数と,それぞれの美術品の大きさと価値が与えられたとき,S −(Amax −Amin)
の最大値を求めよ.
제약
小課題1 [10 点]
• N ≦16 を満たす.
小課題2 [20 点]
• N ≦300 を満たす.
小課題3 [20 点]
• N ≦5000 を満たす.
小課題4 [50 点]
• 追加の制限はない.
입력 형식
標準入力から以下の入力を読み込め.
• 1 行目には,整数N が書かれている.これは,展示される美術品の候補の個数を表す.
• 続くN 行のうちのi 行目(1 ≦i ≦N) には,2 個の整数Ai, Bi が空白を区切りとして書かれている.こ
れらは,美術品i の大きさがAi,価値がBi であることを表す.
출력 형식
標準出力に,S −(Amax −Amin) の最大値を1 行で出力せよ.
第17 回日本情報オリンピック(JOI 2017/2018) 本選
2018 年2 月11 日(茨城県つくば市)
制限
すべての入力データは以下の条件を満たす.
• 2 ≦N ≦500 000.
• 1 ≦Ai ≦1 000 000 000 000 000 = 1015 (1 ≦i ≦N).
• 1 ≦Bi ≦1 000 000 000 (1 ≦i ≦N).
예제 1
입력
3
2 3
11 2
4 5
출력
6
예제 2
입력
6
4 1
1 5
10 3
9 1
4 2
5 3
출력
7
예제 3
입력
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
문제 정보