Pagini recente » Cod sursa (job #1649071) | Cod sursa (job #860770) | Cod sursa (job #1854814) | Cod sursa (job #20890) | Cod sursa (job #669085)
Cod sursa(job #669085)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#define inf 1000000000
#define NM 100005
using namespace std;
int N, K, S[NM], A[NM], PS[NM], W[NM];
int main()
{
freopen ("secv2.in", "r", stdin);
freopen ("secv2.out", "w", stdout);
scanf ("%d %d", &N, &K);
for (int i = 1; i <= N; ++i) scanf ("%d", &S[i]);
for (int i = 1; i <= N; ++i) PS[i] = PS[i-1] + S[i];
for (int i = 1; i <= N; ++i)
if (A[i-1] <= 0)
{
A[i] = S[i];
W[i] = i;
}
else
{
A[i] = A[i-1] + S[i];
W[i] = W[i-1];
}
int best = -inf, start, stop;
for (int i = K; i <= N; ++i)
{
if (PS[i] - PS[i-K] > best)
{
best = PS[i] - PS[i-K];
start = i - K + 1;
stop = i;
}
if (PS[i] - PS[i-K] + A[i-K] > best)
{
best = PS[i] - PS[i-K] + A[i-K];
start = W[i-K];
stop = i;
}
}
printf ("%d %d %d", start, stop, best);
return 0;
}