Cod sursa(job #659922)

Utilizator federerUAIC-Padurariu-Cristian federer Data 11 ianuarie 2012 11:27:13
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include<fstream>
using namespace std;

long long v[50001], best[50001], sol[50001], s[50001], i, k, n, M, poz, S;

ifstream fin("secv2.in");
ofstream fout("secv2.out");

int main()
{
	fin>>n>>k;
	for(i=1;i<=n;i++)
	{
		fin>>v[i];
		s[i]=s[i-1]+v[i];
	}
	for(i=1;i<=n;i++)
		if(v[i]>best[i-1]+v[i])
			best[i]=v[i];
		else
			best[i]=best[i-1]+v[i];
	
	for(i=k;i<=n;i++)
	{
		if(s[i]-s[i-k]>s[i]-s[i-k]+best[i-k])
			sol[i]=s[i]-s[i-k];
		else
			sol[i]=s[i]-s[i-k]+best[i-k];
		if(M<sol[i])
		{
			M=sol[i];
			poz=i;
		}
	}
	S=sol[poz];
	i=poz;
	while(S!=0)
	{
		S-=v[i];
		i--;
	}
	fout<<i+1<<' '<<poz<<' '<<sol[poz]<<'\n';
	fin.close();
	fout.close();
	return 0;
}