Codeforces 2028C. 双指针2
原题链接
简单
作者:
Dessa
,
2024-11-12 19:17:50
,
所有人可见
,
阅读 2
妙写法
const int N = 2e5 + 10;
int a[N];
int b[N];
int c[N];
int l[N], r[N];
void solve()
{
int n, m, v;
cin >> n >> m >> v;
for (int i = 1; i <= n; i++) cin >> a[i], b[i] = b[i - 1] + a[i];
int ans = 0;
int lh = 0;
for (int i = 1; i <= n; i++)
{
ans += a[i];
if (ans >= v) l[++lh] = i, ans = 0;
}
ans = 0;
int rh = 0;
for (int i = n; i >= 1; i--)
{
ans += a[i];
if (ans >= v) r[++rh] = i, ans = 0;
}
if (lh < m && rh < m)
{
cout << "-1" << '\n';
return;
}
int mmax = 0;
r[0] = n + 1;
//l[m] = 0;
for (int i = 0; i <= m; i++)
{
int x = l[i], y = r[m - i];
if (x < y) mmax = max(mmax, b[y - 1] - b[x]);
}
cout << mmax << '\n';
}