Cod sursa(job #307706)

Utilizator pcinfoCarmen Popescu pcinfo Data 24 aprilie 2009 19:52:42
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream f("secv2.in");
ofstream g("secv2.out");

int main()
{
	int n,k,min,max,lung,nr,ult,i;
	f>>n>>k;
	vector<int> s(n+1,0);
	
	for (i=1;i<=n;i++)
	{
		f>>s[i];
		s[i]=s[i]+s[i-1];
	}
	
	min=0; nr=0;
	max=s[k]; lung=k; ult=k;
	
	for (i=k+1;i<=n;i++)
		// suma subsirului cu k elemente ce se termina cu a[i] este s[i]-s[i-k]
		// deci pentru a gasi suma maxima cu cel putin k elemente ce se termina cu elementul i
        // trebuie sa gasim 
		//     max{s[i]-s[i-k], s[i]-s[i-k-1],..., s[i]-s[1], s[i]} = 
        //   = s[i]-min{s[i-k],s[i-k-1],...,s[1],0}
	{
		if (s[i-k]<min)
		{
			min=s[i-k]; nr=i-k;
		}
		if (s[i]-min>max)
		{
			max=s[i]-min;
			ult=i; lung=i-nr;
		}
	}
	
	g<<ult-lung+1<<" "<<ult<<" "<<max;

	g.close();
	return 0;
}