問題一覧 > 通常問題

No.3612 Breaking door keys (ALL BREAK ver.)

レベル : / AI推定難易度 : 235 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 50
作問者 : kazuppa / テスター : Unbakedbread Tamiji153
お気に入りにしたユーザー ProblemId : 13607 / 自分の提出
問題文最終更新日: 2026-08-06 14:08:43
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Paken新入生コンday1 (順位表) の他の問題:

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 160 points$N\leq2000,\ Q\leq2000$
Subtask 260 points$L_i=1$
Subtask 330 pointsNo 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もしくは右上の雲マークをクリックしてアカウントを作成してください。