시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB51322259.459%

문제

Some call you lazy, others (yourself included) call you a break optimizer.

You have been tasked with a large number of chores around your house. The tasks vary greatly in difficulty---some literally only take a second, like putting a fork the dishwasher; others require a lot more effort, like cleaning the drain.

Each task has a difficulty, which is the number of seconds it takes you to complete the task when you are fully rested. Whenever you complete a task and directly start another, its completion time doubles. Formally, completing a task with difficulty $d$ after $i$ tasks before it, without any intervening breaks, takes $ d \cdot 2^i $ seconds.

However, whenever you take a solid break of at least one hour, you become fully rested. (Shorter breaks don’t do anything for you.)

For instance, here are two (suboptimal) ways of scheduling the four tasks in sample $3$:

In both schedules, task 3 takes $2^2\cdot 1000=4000$ seconds.

You have to complete all tasks, in any order. You begin fully rested. What is the shortest time to complete all tasks, including breaks?

입력

The first line contains the number $1 \leq n \leq 100\,000$ of tasks to complete. The second line consists of $n$ integers $d_1, \ldots , d_n$, the difficulty of each task in seconds, where $1 \leq d_i \leq 28\,800$.

출력

Output a single integer, the minimal time in seconds it takes for you to complete all tasks, including your breaks.

서브태스크

번호배점제한
125

$n\leq 1\,000$

210

$d_1=\cdots = d_n$

365

none

예제 입력 1

2
300 400

예제 출력 1

1000

예제 입력 2

3
1000 1100 1000

예제 출력 2

7100

예제 입력 3

4
1000 1100 1000 800

예제 출력 3

9300

예제 입력 4

12
1 1 1 1 1 1 1 1 1 1 1 1

예제 출력 4

3726

예제 입력 5

13
1 1 1 1 1 1 1 1 1 1 1 1 1

예제 출력 5

3790

출처

Contest > Swedish Coding Cup > LTH Challenge 2022 F번

  • 문제를 만든 사람: Måns Magnusson

채점 및 기타 정보

  • 예제는 채점하지 않는다.