尝试二分答案，问题变为要求恰好选 \(x\) 段 \(\ge s\)，最大化选的段数。
发现我们不是很会算段数的 \(\max\)，因为要求段不重不漏地覆盖 \([1, n]\)。考虑给每个 \(\ge s\) 段 \([l, r]\) 一个 \(r - l\) 的代价，于是变成了算代价的 \(\min\)。此时不再要求段不重不漏地覆盖，因为我们可以把没被覆盖的部分接到旁边的 \(\ge s\) 段。
设 \(f(x)\) 为选出恰好 \(x\) 个 \(\ge s\) 的段，每一段 \([l, r]\) 的代价定义为 \(r - l\)，代价的 \(\min\)。那么一个答案 \(x\) 合法当且仅当 \(f(x) \le n - k\)。
发现 \(f(x)\) 下凸（感性理解就是选的段的代价会越来越大），那么 \((x, f(x))\) 构成一个下凸包的右半边（即斜率 \(> 0\) 的部分）。套路地 wqs 二分斜率 \(k\)，选一段的代价变成 \(r - l - k\)，在此基础上求选出若干段的代价 \(\min\) 和在取到这个 \(\min\) 的前提下至少选了多少段即可。
上面那个问题显然可以 dp 求出。dp 数组单调，所以只用考虑最近的一个合法转移点转移过来（即对于每个 \(i\) 满足 \(\sum\limits_{k = j}^i a_k \ge s\) 的最小的 \(j\)）即可。
预处理每个位置的最近合法转移点，总时间复杂度 \(O(n \log^2 n)\)。
code
// Problem: E - Subsegments with Large Sums
// Contest: AtCoder - ALGO ARTIS Programming Contest 2023 Autumn（AtCoder Regular Contest 168）
// URL: https://atcoder.jp/contests/arc168/tasks/arc168_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 250100;
ll n, m, K, a[maxn], b[maxn], p[maxn];
pii f[maxn];
inline pii solve(ll x) {
for (int i = 1; i <= n; ++i) {
f[i] = f[i - 1];
if (p[i]) {
f[i] = min(f[i], mkp(f[p[i] - 1].fst + i - p[i] - x, f[p[i] - 1].scd + 1));
}
}
return f[n];
}
inline bool check(ll x) {
ll l = 0, r = n, pos = -1;
while (l <= r) {
ll mid = (l + r) >> 1;
if (solve(mid).scd <= x) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return solve(pos).fst + x * pos <= n - K;
}
void solve() {
scanf("%lld%lld%lld", &n, &K, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
b[i] = b[i - 1] + a[i];
}
for (int i = 1, j = 0; i <= n; ++i) {
while (b[i] - b[j] >= m) {
++j;
}
p[i] = j;
}
ll l = 0, r = K, ans = -1;
while (l <= r) {
ll mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}