Cod sursa(job #221875)

Utilizator mISHOOOmISHOOO mISHOOO Data 18 noiembrie 2008 18:09:44
Problema Secventa 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <stdio.h>
#define NMAX 50000

FILE *fi = fopen("secv2.in", "r");
FILE *fo = fopen("secv2.out", "w");

int V[NMAX], S[NMAX], M[NMAX], P[NMAX];
int N, K, A, B, min, i, j, t;
long L;

int main() {
	fscanf(fi, "%d%d", &N, &K);
	fscanf(fi, "%d", &V[0]);

	min = V[0];

	M[0] = min;
	P[0] = 0;
	S[0] = V[0];

	for (i=1; i<N; i++) {
		fscanf(fi, "%d", &V[i]);
		S[i] = S[i-1]+V[i];

		if (S[i]<min) {
			min = S[i];
			P[i] = i;
		}
		else P[i] = P[i-1];

		M[i] = min;			
	}

	fclose(fi);
	L = -2147483648;

	for (i=0; i<N; i++) {
		j = P[i];
		while (i-P[j]<K && j>=0) j--;
		
		if (j==-1) t = 0;
		else t=M[j];
		if (S[i]-t>L && i-j>=K && j>=-1) {
			L = S[i] - t;
			B = i+1;
			A = j+2;
		}
	}

	fprintf(fo, "%d %d %d\n", A, B, L);
	fclose(fo);
	return 0;
}