Cod sursa(job #337050)

Utilizator iulia609fara nume iulia609 Data 2 august 2009 13:29:54
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include<stdio.h>
#define dim 50001
using namespace std;

int v[dim], min[dim];
long long S[dim];

long long minim(int a, int b)
{
	if(S[a] <= S[b]) return a;
	return b;
}


int main()
{  int n, k, i, p1, p2;
   long long max;

	FILE *f = fopen("secv2.in", "r");
	FILE *g = fopen("secv2.out", "w");
	
	fscanf(f, "%d%d", &n, &k);
	for(i = 1; i <= n; i++)
		{
			fscanf(f, "%d", &v[i]);
			S[i] = S[i-1] + v[i];
			min[i] = minim(i, min[i-1]);
		}
	
	max = -25001;
	for(i = n; i >= k; i--)
		{
			if(S[i] - S[min[i-k+1]] > max) max = S[i] - S[min[i-k+1]], p1 = min[i-k+1]+1, p2 = i;
		}
	
	
	fprintf(g, "%d %d %lld\n", p1, p2, max);
	
	fclose(f);
	fclose(g);
	return 0;
}