No.3612 Breaking door keys (ALL BREAK ver.)
タグ : / 解いたユーザー数 50
作問者 :
kazuppa
/ テスター :
Introduction
This problem has the same statement as Breaking door keys (LITTLE 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 destroy their locks.
In doing so, you consume stamina equal to the sum of the strengths of the destroyed locks. Specifically, when you destroy the locks of doors $p_1,p_2,...,p_k$, you consume $\displaystyle\sum_{i=1}^k S_{p_i}$ stamina.
Find the minimum stamina required to destroy the locks when the doors are chosen appropriately.
There are $Q$ situations to consider for this problem. For the $i$-th situation, answer the problem with $l=L_i,r=R_i,k=K_i$.
Constraints
- $1\leq N\leq 2\times 10^5$
- $1\leq S_i\leq 10^9$
- $1\leq Q \leq 2\times 10^5$
- $1\leq L_i\leq R_i\leq N$
- $\color{red}{K_i=R_i-L_i+1}$
- All input values are integers.
Subtasks
This problem has partial scoring by subtasks.
| Subtask | Points | Constraints |
|---|---|---|
| Subtask 1 | 60 points | $N\leq2000,\ Q\leq2000$ |
| Subtask 2 | 60 points | $L_i=1$ |
| Subtask 3 | 30 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
3 3 9 4 5 1 2 2 1 3 3 3 3 1
Output
13 18 5
- For situation number $1$, choosing doors $1,2$ consumes $9+4=13$ stamina.
- For situation number $2$, choosing doors $1,2,3$ consumes $9+4+5=18$ stamina.
- For situation number $3$, choosing door $3$ consumes $5$ stamina.
This case satisfies the constraints of Subtasks 1,3.
Sample 2
Input
6 3 1 6 9 2 3 1 1 2 2 1 3 3 1 6 6
Output
7 16 22
This case satisfies the constraints of all subtasks.
Sample 3
Input
10 10 642323305 764287637 550312118 577593161 37991786 723146696 964957968 527248326 846898844 212337789 8 10 3 4 8 5 7 10 4 9 10 2 7 9 3 2 4 3 6 7 2 3 8 6 3 7 5 6 9 4
Output
1586484959 2830937937 2551442927 1059236633 2339105138 1892192916 1688104664 3381250055 2854001729 3062251834
This case satisfies the constraints of Subtasks 1,3.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。