/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
長さ N の正整数列 A=(A_1,A_2,\cdots,A_N) が与えられます．
この数列を K 個の非空な連続部分列に分割することを考えます． この K 個の連続部分列のうち，要素の総和が S 以上であるものの個数をスコアと呼ぶことにします． スコアの最大値を求めてください．
制約
- 1 \leq K \leq N \leq 250000
- 1 \leq A_i \leq 10^9
- 1 \leq S \leq 10^{15}
- 入力される値はすべて整数．
入力
入力は以下の形式で標準入力から与えられる．
N K S A_1 A_2 \cdots A_N
出力
答えを出力せよ．
入力例 1
4 3 6 1 4 2 8
出力例 1
2
数列を (1),(4,2),(8) と分割すると，スコアが 2 になります． これより大きいスコアは達成できないため，答えは 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
Score : 800 points
Problem Statement
You are given a sequence of positive integers A=(A_1,A_2,\cdots,A_N) of length N.
Consider dividing this sequence into K non-empty contiguous subsequences. Among these K contiguous subsequences, the number of ones whose sum of elements is at least S will be called the score. Find the maximum value of the score.
Constraints
- 1 \leq K \leq N \leq 250000
- 1 \leq A_i \leq 10^9
- 1 \leq S \leq 10^{15}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K S A_1 A_2 \cdots A_N
Output
Print the answer.
Sample Input 1
4 3 6 1 4 2 8
Sample Output 1
2
If the sequence is divided into (1),(4,2),(8), the score will be 2. No higher score can be achieved, so the answer is 2.
Sample Input 2
10 5 2 1 1 1 1 1 1 1 1 1 1
Sample Output 2
5
Sample Input 3
10 5 3 1 1 1 1 1 1 1 1 1 1
Sample Output 3
2
Sample Input 4
20 6 946667802 786820955 250480341 710671229 946667801 19271059 404902145 251317818 22712439 520643153 344670307 274195604 561032101 140039457 543856068 521915711 857077284 499774361 419370025 744280520 249168130
Sample Output 4
6