시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 51 | 32 | 22 | 59.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.
번호 | 배점 | 제한 |
---|---|---|
1 | 25 | $n\leq 1\,000$ |
2 | 10 | $d_1=\cdots = d_n$ |
3 | 65 | none |
2 300 400
1000
3 1000 1100 1000
7100
4 1000 1100 1000 800
9300
12 1 1 1 1 1 1 1 1 1 1 1 1
3726
13 1 1 1 1 1 1 1 1 1 1 1 1 1
3790
Contest > Swedish Coding Cup > LTH Challenge 2022 F번