Cod sursa(job #846437)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 2 ianuarie 2013 10:37:51
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdlib.h>
using namespace std;

ifstream fi ("secv2.in");
ofstream fo ("secv2.out");

const int dim = 50005, OO = (1<<31)-1;
int N, K, S, SA, R, P, U, PC, PC2, A[dim], Pp[dim];

int main ()
{
	fi >> N >> K;
	S = -1;
	R = -OO;
	for (int i = 1; i <= N; i++)
	{
		fi >> A[i];
		Pp[i] = Pp[i-1] + A[i];
		
		if (S >= 0)
		{
			S += A[i];
		}
		else
		{
			S = A[i];
			PC = i;
		}
		
		PC2 = i - K + 1;
		if (PC2 >= 1) 
		{
			SA = 0;
			if (PC2 < PC)
				SA = Pp[PC-1] - Pp[PC2-1];
			
			if (R < S + SA)
			{
				R = S + SA;
				P = min (PC, PC2);
				U = i;
			}
		}
	}
	fo << P << ' ' << U << ' ' << R << ' ';
	return 0;
}