[ARC168E] Subsegments with Large Sums
题意翻译
给定长度为 $n$ 的数列 $\{a_i\}$ 和两个参数 $k, s$,将 $\{a_i\}$ 划分成 $k$ 段,最大化和 $\geq s$ 的段数。
第一行三个数 $n, k, s$,第二行 $n$ 个数 $\{a_i\}$。
输出一个数,代表和不小于 $s$ 的段的数量。
$1 \leq k \leq n \leq 250000, 1 \leq A_i \leq 10^9, 1 \leq s \leq 10^{15}$。
题目描述
[problemUrl]: https://atcoder.jp/contests/arc168/tasks/arc168_e
長さ $ N $ の正整数列 $ A=(A_1,A_2,\cdots,A_N) $ が与えられます.
この数列を $ K $ 個の非空な連続部分列に分割することを考えます. この $ K $ 個の連続部分列のうち,要素の総和が $ S $ 以上であるものの個数を**スコア**と呼ぶことにします. スコアの最大値を求めてください.
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる.
> $ N $ $ K $ $ S $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $
输出格式
答えを出力せよ.
输入输出样例
输入样例 #1
4 3 6
1 4 2 8
输出样例 #1
2
输入样例 #2
10 5 2
1 1 1 1 1 1 1 1 1 1
输出样例 #2
5
输入样例 #3
10 5 3
1 1 1 1 1 1 1 1 1 1
输出样例 #3
2
输入样例 #4
20 6 946667802
786820955 250480341 710671229 946667801 19271059 404902145 251317818 22712439 520643153 344670307 274195604 561032101 140039457 543856068 521915711 857077284 499774361 419370025 744280520 249168130
输出样例 #4
6
说明
### 制約
- $ 1\ \leq\ K\ \leq\ N\ \leq\ 250000 $
- $ 1\ \leq\ A_i\ \leq\ 10^9 $
- $ 1\ \leq\ S\ \leq\ 10^{15} $
- 入力される値はすべて整数.
### Sample Explanation 1
数列を $ (1),(4,2),(8) $ と分割すると,スコアが $ 2 $ になります. これより大きいスコアは達成できないため,答えは $ 2 $ です.