No.3614 Breaking door keys (LITTLE BREAK ver.)
タグ : / 解いたユーザー数 41
作問者 :
kazuppa
/ テスター :
Introduction
This problem has the same statement as Breaking door keys (ALL BREAK ver.), but the constraint on $K_i$ is different.
Problem Statement
$N$ doors are lined up in a row. Door $i$ has a lock of strength $S_i$.
Now, consider the following problem.
You will choose $k$ of the doors $i$ satisfying $l\leq i\leq r$ and break their locks.
Doing so consumes stamina equal to the sum of the strengths of the broken locks. Specifically, breaking the locks of doors $p_1,p_2,...,p_k$ consumes $\displaystyle\sum_{i=1}^k S_{p_i}$ stamina.
Find the minimum stamina required to break the locks when the doors are chosen appropriately.
There are $Q$ situations to consider for this problem. For the $i$-th situation, answer this problem with $l=L_i,r=R_i,k=K_i$.
Constraints
- $1\leq N\leq 10^5$
- $1\leq Q\leq 10^5$
- $1\leq S_i\leq 10^9$
- $1\leq L_i\leq R_i\leq N$
- $\color{red}{1\leq K_i \leq \min(10,R_i-L_i+1)}$
- All input values are integers.
Subtasks
This problem has partial scoring by subtasks.
| Subtask | Score | Constraints |
|---|---|---|
| Subtask 1 | 25 points | $N\leq500,\ Q\leq500$ |
| Subtask 2 | 50 points | $L_i=1$ |
| Subtask 3 | 75 points | $K_i=1$ |
| Subtask 4 | 75 points | $K_i\leq2$ |
| Subtask 5 | 25 points | No additional constraints |
Input
$N\ Q$ $S_1\ S_2\ \dotsc \ S_N$ $L_1\ R_1\ K_1$ $L_2\ R_2\ K_2$ $\vdots$ $L_Q\ R_Q\ K_Q$
Output
Output $Q$ lines.
On the $i$-th line, output the answer for the $i$-th situation.
Sample
Sample 1
Input
6 3 1 6 9 2 3 1 1 3 2 2 4 1 1 6 2
Output
7 2 2
- For the $1$-st situation, choosing doors $1,2$ consumes $1+6=7$ stamina.
- For the $2$-nd situation, choosing door $4$ consumes $2$ stamina.
- For the $3$-rd situation, choosing doors $1,6$ consumes $2$ stamina.
This case satisfies the constraints of Subtasks 1,4,5.
Sample 2
Input
6 3 4 1 1 8 9 2 4 6 1 2 3 1 1 6 1
Output
2 1 1
This case satisfies the constraints of Subtasks 1,3,4,5.
Sample 3
Input
6 3 3 1 4 1 5 9 1 5 3 1 4 4 1 6 2
Output
5 9 2
This case satisfies the constraints of Subtasks 1,2,5.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。