Daddy's Journey to Platinum

There are n books, and Kotivalo and Justiina are going to read them all. For each book, you know the time it takes to read it.

They both read each book from beginning to end, and they cannot read a book at the same time. What is the minimum total time required?

The first input line has an integer n: the number of books.

The second line has n integers t_1,t_2,…,t_n : the time required to read each book.

Print one integer: the minimum total time.

3
2 8 3

16

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

가장 긴책을 읽는 동안 다른 책들을 모두 읽을 수 있으면, 가장 긴책을 읽는 시간 * 2, 아니면, 나머지 책을 읽는 시간 + 가장 긴책을 읽는 시간이 된다.

A factory has n machines which can be used to make products. Your goal is to make a total of t products.

For each machine, you know the number of seconds it needs to make a single product. The machines can work simultaneously, and you can freely decide their schedule.

What is the shortest time needed to make tt products?

The first input line has two integers n and t: the number of machines and products.

The next line has n integers k_1,k_2,…,k_n : the time needed to make a product using each machine.

Print one integer: the minimum time needed to make t products.

3 7
3 2 5

8

Explanation: Machine 1 makes two products, machine 2 makes four products and machine 3 makes one product

• 1 <= n <= 2x10^5
• 1 <= t <= 10^9 
• 1 <= k_i <= 10^9

여러 기계를 동시에 돌려서 필요한 물건을 가장 빨리 만드는 시간을 찾는 문제이다.

가장 최악의 경우는 제일 오래 걸리는 기계가 모든 물건을 만드는 경우이고, 이것보다는 빨리 만들거라고 생각하고 이진 탐색을 한다. 특정 시간동안 만들어진 물건의 수를 확인해서 필요한 물건보다 많이 만들면 시간을 단축하고 부족하면 늘리는 방법으로 1/2 비율로 줄여나가서 필요한 물건과 같아질때 시간을 출력한다.

There is a large hotel, and n customers will arrive soon. Each customer wants to have a single room.

You know each customer's arrival and departure day. Two customers can stay in the same room if the departure day of the first customer is earlier than the arrival day of the second customer.

What is the minimum number of rooms that are needed to accommodate all customers? And how can the rooms be allocated?

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

Then there are n lines, each of which describes one customer. Each line has two integers a and b: the arrival and departure day.

Print first an integer kk: the minimum number of rooms required.

After that, print a line that contains the room number of each customer in the same order as in the input. The rooms are numbered 1,2,…,k 

3
1 2
2 4
4 4

2
1 2 1

• 1 <= n <= 2x10^5
• 1 <= a <= b <= 10^9

도착일, 출발일과 몇번째 손님인지 저장해서, 도착일 순으로 정렬한다.

출발일과 몇개의 방이 사용중인지 priority queue 에 저장하고, 가장 빠른 출발일과 새로운 도착일을 비교해서 사용중인 방의 수를 변경한다.

There is a street of length x whose positions are numbered 0,1,…,x. Initially, there are no traffic lights, but n sets of traffic lights are added to the street one after another.

Your task is to calculate the length of the longest passage without traffic lights after each addition.

The first input line contains two integers x and n: the length of the street and the number of sets of traffic lights.

Then, the next line contains n integers p_1,p_2,…,p_n : the position of each set of traffic lights. Each position is distinct.

8 3
3 6 2

Print the length of the longest passage without traffic lights after each addition.

5 3 3

• 1 ≤ x ≤ 10^9
• 1 ≤ n ≤2x10^^5
• 0 < p_i < x

입력받은 가로등 위치를 set에 입력하고, 원래 있던 가로등 위치에서 가장 가까운 가로등 위치를 찾아서 간격을 계산한다. 

You have to process n tasks. Each task has a duration and a deadline, and you will process the tasks in some order one after another. Your reward for a task is d−f where d is its deadline and f is your finishing time. (The starting time is 0, and you have to process all tasks even if a task would yield negative reward.)

What is your maximum reward if you act optimally?

The first input line has an integer n: the number of tasks.

After this, there are n lines that describe the tasks. Each line has two integers a and d: the duration and deadline of the task.

Print one integer: the maximum reward.

3
6 10
8 15
5 12

2

• 1 <= n  <= 2x10^5
• 1 <= a,d  <= 10^6

입력받은 업무를 필요 시간을 기준으로 정렬한다.

일은 같이 진행할 수 없기 때문에 전체 업무를 끝내는 시간은 필요 시간 전체의 합으로 고정되어 있으므로, 보상이 큰 일을 먼저 하도록 한다. 필요시간이 짧은 순서로 보상을 계산하기 위해서, 처음부터 진행한 시간과 보상을 기록해서 출력한다.

You are given n cubes in a certain order, and your task is to build towers using them. Whenever two cubes are one on top of the other, the upper cube must be smaller than the lower cube.

You must process the cubes in the given order. You can always either place the cube on top of an existing tower, or begin a new tower. What is the minimum possible number of towers?

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

The next line contains n integers k_1,k_2,…,k_n: the sizes of the cubes.

Print one integer: the minimum number of towers.

5
3 8 2 1 5

2

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

몇개의 탑이 있고, 그 마지막값이 얼마인지 검색하는 문제이다.

입력받은 블럭의 크기보다 마지막 값이 큰 탑이 있는지 검색하고, 있으면 새로운 블럭 크기로 바꾸고, 없으면 새로운 탑을 만든다. 입력이 끝나면, 탑의 수를 출력한다.

You are given a playlist of a radio station since its establishment. The playlist has a total of n songs.

What is the longest sequence of successive songs where each song is unique?

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

The next line has n integers k)1,k_2,…,k_n: the id number of each song.

Print the length of the longest sequence of unique songs.

8
1 2 1 3 2 7 4 2

5

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

입력받은 노래 목록을 set에 저장하며 중복목록을 확인한다. 중복목록이 나오면, 중복목록이 나오기 전에 있는 목록들을 지운다. 

노래 목록이 끝나면, set의 크기를 출력한다.

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 출력한다.