Cod sursa(job #669085)

Utilizator JBaccountCatalin JBaccount Data 26 ianuarie 2012 03:34:22
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#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;
}