Cod sursa(job #486891)

Utilizator dcm9000Dinu Cristian Mircea - UPB dcm9000 Data 23 septembrie 2010 02:45:28
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

#define FILE_IN "secv2.in"
#define FILE_OUT "secv2.out"

int N,K;
int V[50000];
int S[50000]; //S[K] = suma(V[0]..V[K])
int M[50000]; //M[K] = min(S[0]..S[K-1])

int main()
{
	FILE* fisIn = fopen(FILE_IN, "r");
	ofstream fisOut(FILE_OUT);

	static char linie[360000];
	fscanf(fisIn, "%d %d", &N, &K);
	fgets(linie, 360000, fisIn);
	fgets(linie, 360000, fisIn);

	char* ptr = linie;
	char* ptr2;
	for (int i=0; i<N; i++)
	{
		V[i] = strtol(ptr, &ptr2, 10);
		ptr = ptr2;
	}

	int suma = 0;
	int mi = 0;
	for (int i=0; i<N; i++)
	{
		suma += V[i];
		S[i] = suma;
		M[i] = mi;
		if (suma < mi) mi = suma;
	}

	int best = 0x80000000;
	int end;
	for (int i=K; i<N; i++)
		if (S[i]-M[i-K] > best)
		{
			best = S[i]-M[i-K];
			end = i;
		}

	int start;
	for (start=0; start<=K; start++)
		if (S[end]-M[start] == best) break;

	fisOut << (start+1) << " " << (end+1) << " " << best << "\n";
}