{"problem":{"name":"Subsegments with Large Sums","description":{"content":"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 subsequence","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc168_e"},"statements":[{"statement_type":"Markdown","content":"You are given a sequence of positive integers $A=(A_1,A_2,\\cdots,A_N)$ of length $N$.\nConsider 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.\n\n## Constraints\n\n*   $1 \\leq K \\leq N \\leq 250000$\n*   $1 \\leq A_i \\leq 10^9$\n*   $1 \\leq S \\leq 10^{15}$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $K$ $S$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc168_e","tags":[],"sample_group":[["4 3 6\n1 4 2 8","2\n\nIf 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$."],["10 5 2\n1 1 1 1 1 1 1 1 1 1","5"],["10 5 3\n1 1 1 1 1 1 1 1 1 1","2"],["20 6 946667802\n786820955 250480341 710671229 946667801 19271059 404902145 251317818 22712439 520643153 344670307 274195604 561032101 140039457 543856068 521915711 857077284 499774361 419370025 744280520 249168130","6"]],"created_at":"2026-03-03 11:01:14"}}