Cod sursa(job #519076)

Utilizator ChallengeMurtaza Alexandru Challenge Data 3 ianuarie 2011 22:22:17
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>

using namespace std;

const char InFile[]="secv2.in";
const char OutFile[]="secv2.out";
const int MaxN=50111;
const int MAX=2000111000;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,K,best[MaxN],best_st[MaxN],v[MaxN],sol=-MAX,sol_st,sol_end;

int main()
{
	fin>>N>>K;
	for(register int i=1;i<=N;++i)
	{
		fin>>v[i];
	}
	fin.close();

	for(register int i=1;i<=N;++i)
	{
		best[i]=v[i];
		best_st[i]=i;
		if(best[i-1]>0)
		{
			best[i]+=best[i-1];
			best_st[i]=best_st[i-1];
		}
	}

	int sum=0;
	for(register int i=1;i<K;++i)
	{
		sum+=v[i];
	}

	for(register int i=K;i<=N;++i)
	{
		sum-=v[i-K];
		sum+=v[i];
		if(sol<sum)
		{
			sol=sum;
			sol_end=i;
			sol_st=i-K+1;
		}
		if(sol<sum+best[i-K])
		{
			sol=sum+best[i-K];
			sol_end=i;
			sol_st=best_st[i-K];
		}
	}

	fout<<sol_st<<" "<<sol_end<<" "<<sol;
	fout.close();
	return 0;
}