쌍둥이 Antanas와 Bronius는 생일 선물로 큰 쿠키 상자를 받았습니다. 상자에는 총 N개의 서로 다른 쿠키가 있으며, 1부터 N까지 번호가 매겨져 있습니다.
쌍둥이들은 모든 쿠키를 똑같이 좋아하지는 않습니다: Antanas는 i번째 쿠키에 ai점을 부여하고, Bronius는 bi점을 부여합니다. 점수가 높을수록 쿠키를 더 좋아합니다. 두 쌍둥이 모두 각자가 각 쿠키에 부여하는 점수를 알고 있습니다.
엄마는 쌍둥이들에게 다음과 같이 과자를 나누도록 제안했습니다: 먼저 Antanas가 한 쿠키를 선택하고, 그 다음 남은 쿠키 중에서 Bronius가 하나를 선택하고, 이런 식으로 상자가 비워질 때까지 계속합니다.
형제들은 그다지 우호적이지 않기 때문에, 각자는 나눔이 끝났을 때 자신이 선택한 쿠키의 점수 합이 형제의 쿠키 점수 합보다 가능한 한 크게 되도록 쿠키를 선택하려고 합니다.
다시 말해, 나눔 과정에서 Antanas가 선택한 쿠키들의 점수 합을 A, Bronius가 선택한 쿠키들의 점수 합을 B라고 할 때, Antanas의 목표는 나눔이 끝날 때 A - B의 차이를 가능한 크게 만드는 것이고, Bronius의 목표는 B - A의 차이를 가능한 크게 만드는 것입니다.
두 쌍둥이가 최적으로 쿠키를 선택할 때, A-B의 차이가 얼마인지 계산하세요.
입력
첫 번째 줄에는 쿠키의 개수 N이 주어집니다. 그 다음 N개의 줄에는 각각 두 개의 정수가 주어집니다:
ai - Antanas가 i번째 쿠키에 부여하는 점수;
bi - Bronius가 i번째 쿠키에 부여하는 점수;
출력
하나의 정수를 출력하세요 - 쌍둥이들이 최적의 전략으로 쿠키를 나눌 때 A-B의 값을 출력하세요.
서브태스크
번호
배점
제한
1
8
1 ≤ N ≤ 10, 0 ≤ ai, bi ≤ 1 000
2
18
1 ≤ N ≤ 22, 0 ≤ ai, bi ≤ 1 000
3
23
1 ≤ N ≤ 1 000, 0 ≤ ai, bi ≤ 1 000
4
7
1 ≤ N ≤ 200 000, 0 ≤ ai, bi ≤ 1
5
14
1 ≤ N ≤ 200 000, 0 ≤ ai, bi ≤ 1 000, ai = bi
6
30
1 ≤ N ≤ 200 000, 0 ≤ ai, bi ≤ 1 000
예제 입력 1
4
100 1
200 2
400 4
300 3
596
Antanas는 세 번째 쿠키를 선택하고, Bronius는 네 번째 쿠키를 선택한 다음, Antanas는 두 번째 쿠키를 선택하고, 마지막으로 Bronius에게 첫 번째 쿠키가 돌아갑니다.
A = a3 + a2 = 400 + 200 = 600
B = b4 + b1 = 3 + 1 = 4
예제 입력 2
2
10 100
11 50
-40
이 경우 Antanas는 첫 번째 쿠키를 선택하고, Bronius에게는 두 번째 쿠키가 돌아갑니다.
A = a1 = 10
B = b2 = 50
만약 Antanas가 두 번째 쿠키를 선택했다면, A-B는 a2-b1 = 11-100 = -89가 되었을 것이므로, 이는 Antanas에게 최적의 선택이 아닙니다.
hanzch 1년 전
Sausainiai
문제
쌍둥이 Antanas와 Bronius는 생일 선물로 큰 쿠키 상자를 받았습니다. 상자에는 총 N개의 서로 다른 쿠키가 있으며, 1부터 N까지 번호가 매겨져 있습니다.
쌍둥이들은 모든 쿠키를 똑같이 좋아하지는 않습니다: Antanas는 i번째 쿠키에 ai점을 부여하고, Bronius는 bi점을 부여합니다. 점수가 높을수록 쿠키를 더 좋아합니다. 두 쌍둥이 모두 각자가 각 쿠키에 부여하는 점수를 알고 있습니다.
엄마는 쌍둥이들에게 다음과 같이 과자를 나누도록 제안했습니다: 먼저 Antanas가 한 쿠키를 선택하고, 그 다음 남은 쿠키 중에서 Bronius가 하나를 선택하고, 이런 식으로 상자가 비워질 때까지 계속합니다.
형제들은 그다지 우호적이지 않기 때문에, 각자는 나눔이 끝났을 때 자신이 선택한 쿠키의 점수 합이 형제의 쿠키 점수 합보다 가능한 한 크게 되도록 쿠키를 선택하려고 합니다.
다시 말해, 나눔 과정에서 Antanas가 선택한 쿠키들의 점수 합을 A, Bronius가 선택한 쿠키들의 점수 합을 B라고 할 때, Antanas의 목표는 나눔이 끝날 때 A - B의 차이를 가능한 크게 만드는 것이고, Bronius의 목표는 B - A의 차이를 가능한 크게 만드는 것입니다.
두 쌍둥이가 최적으로 쿠키를 선택할 때, A-B의 차이가 얼마인지 계산하세요.
입력
첫 번째 줄에는 쿠키의 개수 N이 주어집니다. 그 다음 N개의 줄에는 각각 두 개의 정수가 주어집니다:
출력
하나의 정수를 출력하세요 - 쌍둥이들이 최적의 전략으로 쿠키를 나눌 때 A-B의 값을 출력하세요.
서브태스크
예제 입력 1
Antanas는 세 번째 쿠키를 선택하고, Bronius는 네 번째 쿠키를 선택한 다음, Antanas는 두 번째 쿠키를 선택하고, 마지막으로 Bronius에게 첫 번째 쿠키가 돌아갑니다.
A = a3 + a2 = 400 + 200 = 600
B = b4 + b1 = 3 + 1 = 4
예제 입력 2
이 경우 Antanas는 첫 번째 쿠키를 선택하고, Bronius에게는 두 번째 쿠키가 돌아갑니다.
A = a1 = 10
B = b2 = 50
만약 Antanas가 두 번째 쿠키를 선택했다면, A-B는 a2-b1 = 11-100 = -89가 되었을 것이므로, 이는 Antanas에게 최적의 선택이 아닙니다.