問題一覧 > 通常問題

No.3614 Breaking door keys (LITTLE BREAK ver.)

レベル : / AI推定難易度 : 1425 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 41
作問者 : kazuppa / テスター : Unbakedbread Tamiji153
お気に入りにしたユーザー ProblemId : 13608 / 自分の提出
問題文最終更新日: 2026-08-06 14:09:36
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 (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 125 points$N\leq500,\ Q\leq500$
Subtask 250 points$L_i=1$
Subtask 375 points$K_i=1$
Subtask 475 points$K_i\leq2$
Subtask 525 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
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もしくは右上の雲マークをクリックしてアカウントを作成してください。