Cod sursa(job #266961)

Utilizator katakunaCazacu Alexandru katakuna Data 26 februarie 2009 14:40:12
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<stdio.h>
#include<algorithm>
#define nmax 50111
using namespace std;

int  n,k,v[nmax],m[nmax],s[nmax],i,sol,p,u;

int main(){

	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[1] = v[1];
	m[1] = 1;
	for(i=2; i<=n; i++){
		//m[i] = min(m[i-1],v[i]);
		s[i] = s[i-1] + v[i];
		
		if( s[i] < s[m[i-1]] )
			m[i] = i;
		else
			m[i] = m[i-1];
	}
	
	sol = s[k];
	p = 1;
	u = k;
	for(i=k + 1; i<=n; i++){
		//sol = max(sol, s[i] - m[i-k]);
		if(sol < s[i] - s[m[i-k]]){
			p = m[i-k] + 1;
			u = i;
			sol = s[i] - s[m[i-k]];
		}
		
		if(s[i] > sol){
			sol = s[i];
			p = 1;
			u = i;
		}
	}		
	fprintf(g,"%d %d %d",p,u,sol);
	
	fclose(f);
	fclose(g);

	return 0;
}