시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 684 | 443 | 332 | 66.135% |
$f(x) = ax + b$형태의 일차함수가 $N$개 있다. $i$번째 함수는 $f_i(x) = {a_i}x + {b_i}$로 표현된다.
이 함수들 각각의 $x$에 $1$부터 $N$까지의 서로 다른 정수 $N$개를 하나씩 대입하여 만들 수 있는 $f(x)$들의 합의 최댓값을 구해보자.
구체적으로는, 길이 $N$의 순열 $x_1, x_2, ... x_N$을 적절히 정해 $\sum_{i=1}^N {a_i}{x_i}+{b_i}$의 값을 최대화하여라.
첫째 줄에 일차함수의 개수 $N$이 주어진다. $(1≤N≤100,000)$
둘째 줄부터 $N$줄에 걸쳐 $i$번째 일차함수를 나타내는 두 정수 $a_i, b_i$가 공백으로 구분되어 입력된다. $(0≤a_i, b_i≤ 10^9)$
첫째 줄에 문제의 답을 출력한다.
번호 | 배점 | 제한 |
---|---|---|
1 | 3 | 입력되는 함수 $ax+b$의 모든 $a$는 하나의 수로 같다. |
2 | 87 | $N ≤ 5,000$ |
3 | 10 | 추가 제약 조건 없음 |
5 2 4 5 1 3 2 1 10 0 0
62
High School > 단국대학교부속소프트웨어고등학교 > 단대소프트고 2022 여름대회 B번