Cod sursa(job #671174)

Utilizator micutuzBalog Adrian micutuz Data 30 ianuarie 2012 21:00:46
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include<fstream>
#include<iostream>
#define DN 50005
using namespace std;
int n, k, s[DN], a[DN], m[DN], poz[DN], mn, p, p1, p2, smax=-DN;
int main()
{
	ifstream fin("secv2.in");
	ofstream fout("secv2.out");
	fin>>n>>k;
	for(int i=1;i<=n;++i)
	{ 
		fin>>a[i]; 
		s[i]=s[i-1]+a[i]; 
		if(s[i]<mn)
		{ 
			mn=s[i]; 
			p=i; 
		} 
		m[i]=mn; 
		poz[i]=p; 
	}
    if(n==k)
		fout<<1<<" "<<n<<" "<<s[n];
    else
    {
		for(int i=1;i<=n;++i)     
			if(i-k>0)
				if(s[i]-m[i-k]>smax)
				{
					smax=s[i]-m[i-k];
					p1=poz[i-k]+1;
					p2=i;
				}
		fout<<p1<<" "<<p2<<" "<<smax; 
	}       
}