Pagini recente » Cod sursa (job #1588915) | Cod sursa (job #26717) | Cod sursa (job #1880479) | Cod sursa (job #3147199) | Cod sursa (job #1714074)
#include <iostream>
#include <cstdio>
#define MAXN 50050
using namespace std;
int n, k, a[MAXN];
int sum[MAXN], minsum[MAXN], dsum[MAXN], dmsum[MAXN];
void citire()
{
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%d", a+i);
}
void pre()
{
for (int i = 1; i <= n; i++)
sum[i] = sum[i-1] + a[i];
minsum[1] = 1;
for (int i = 2; i <= n; i++)
if (sum[i] < sum[minsum[i-1]])
minsum[i] = i;
else
minsum[i] = minsum[i-1];
for (int i = n; i; --i)
dsum[i] = dsum[i+1] + a[i];
dmsum[n] = n;
dmsum[n+1] = n+1;
for (int i = n-1; i; --i)
if (dsum[i] < dsum[dmsum[i+1]])
dmsum[i] = i;
else
dmsum[i] = dmsum[i+1];
for (int i = 1; i <= n; i++)
{
if (sum[i] > 0) sum[i] = 0;
if (dsum[i] > 0) dsum[i] = 0;
}
}
void solve()
{
int best = 1000, pos;
for (int i = 0; i <= n-k; i++)
{
int sterg = sum[minsum[i]] + dsum[dmsum[i+k+1]];
if (sterg < best)
{
best = sterg;
pos = i;
}
}
int s = 0;
for (int i = 1; i <= n; i++) s += a[i];
printf("%d %d %d\n", minsum[pos]+1, dmsum[pos+k+1]-1, s - sum[minsum[pos]] - dsum[dmsum[pos+k+1]]);
}
int main()
{
freopen("secv2.in", "r", stdin);
freopen("secv2.out", "w", stdout);
citire();
pre();
solve();
return 0;
}