Pagini recente » Cod sursa (job #2828964) | Cod sursa (job #1936140) | Cod sursa (job #59628) | Cod sursa (job #2077033) | Cod sursa (job #56789)
Cod sursa(job #56789)
#include <iostream>
#include <cstdio>
using namespace std;
#define MaxN 50001
int N, K, A[MaxN];
int best[MaxN], pred[MaxN], sum[MaxN];
int max_sum, start, end;
void read_data(void)
{
FILE *fin = fopen("secv2.in", "rt");
int i;
fscanf(fin, "%d %d ", &N, &K);
for (i = 1; i <= N; i++)
fscanf(fin, "%d ", A+i), sum[i] = A[i] + sum[i-1];
fclose(fin);
}
void solve(void)
{
int i;
best[1] = A[1];
pred[1] = 1;
for (i = 2; i <= N; i++)
if (A[i] > A[i] + best[i-1])
best[i] = A[i], pred[i] = i;
else
best[i] = A[i] + best[i-1], pred[i] = pred[i-1];
max_sum = -(1 << 31);
for (i = K; i <= N; i++)
if (max_sum < sum[i] - sum[i-K+1] + best[i-K+1])
max_sum = sum[i] - sum[i-K+1] + best[i-K+1], start = pred[i-K+1], end = i;
}
void print(void)
{
FILE *fout = fopen("secv2.out", "wt");
fprintf(fout, "%d %d %d", start, end, max_sum);
fclose(fout);
}
int main(void)
{
read_data();
solve();
print();
return 0;
}