Cod sursa(job #1208753)

Utilizator mihaimusatMihai Musat mihaimusat Data 16 iulie 2014 15:26:19
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>

using namespace std;

int n, a[50010], sum[50010], best[50010], inc[50010], k;

int main ()
{
	ifstream f("secv2.in");
	ofstream g ("secv2.out");
	f>>n>>k;
	int i;
	for (i=1; i<=n; i++)
	{
		f>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	best[1]=a[1];
	inc[1]=1;
	for (i=2; i<=n; i++)
	{
		if (a[i]>best[i-1]+a[i])
		{
			best[i]=a[i];
			inc[i]=i;
		}
		else
		{
			best[i]=best[i-1]+a[i];
			inc[i]=inc[i-1];
		}
	}

	int s, maxim=-2000000000, x=1, y=k;
	for (i=k; i<=n; i++)
	{
		s=sum[i]-sum[i-k+1]+best[i-k+1];
		if (s>maxim)
		{
			maxim=s;
			x=inc[i-k+1];
			y=i;
		}
	}
	g<<x<<" "<<y<<" "<<maxim<<"\n";
	return 0;
}