Daddy's Journey to Platinum

There are n sticks with some lengths. Your task is to modify the sticks so that each stick has the same length.

You can either lengthen and shorten each stick. Both operations cost x where x is the difference between the new and original length.

What is the minimum total cost?

The first input line contains an integer n: the number of sticks.

Then there are n integers: p_1,p_2,…,p_n: the lengths of the sticks.

Print one integer: the minimum total cost.

5
2 3 1 5 2

5

• 1 <= n <= 2x10^5
• 1 <= p_i <= 10^9

입력받은 막대 길이를 정렬하고, median 값을 기준으로 비용을 계산한다.

Given an array of n integers, your task is to find the maximum sum of values in a contiguous, nonempty subarray.

The first input line has an integer n: the size of the array.

The second line has n integers x_1, x_2,…,x_n: the array values.

Print one integer: the maximum subarray sum.

8
-1 3 -2 5 3 -5 2 2

9

• 1 <= n <= 2x10^5
• −10^9 <= x_i <= 10^9

배열에 값을 읽어들이면서, 부분합(1~ k) 을 기록한다.

새로운 배열값과 부분합을 비교해서 최대값을 기록한다.

You are given an array of n integers, and your task is to find two values (at distinct positions) whose sum is x.

The first input line has two integers n and x: the array size and the target sum.

The second line has n integers a_1,a_2,…,a_n : the array values.

Print two integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print IMPOSSIBLE.

4 8
2 7 5 1

2 4

• 1 <= n <= 2x10^5
• 1 <= x, a_i <= 10^9

입력받은 문자열의 값과 위치를 저장하고, 값을 기준으로 정렬한다.

양쪽에서 출발해서 맞는 값을 찾는다.

작은 값(left)과 큰 값(right)을 더해서 원하는 값과 비교해서 작으면 (left++), 값이 더 크면 (right--) 진행한다.  

답이 있는면 위치를 출력하고,  해당하는 값이 없는 경우 IMPOSSIBLE 출력한다.