Cod sursa(job #894939)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 27 februarie 2013 01:54:30
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;


const char infile [] ="secv2.in";
const char outfile [] = "secv2.out";

#define MAXN 50002

int A[MAXN];

int N;
int K;

int ResultStart = 0;
int ResultEnd = 0;
int Result = 0;

void citire()
{
	fstream fin(infile, ios::in);


	fin >> N;
	fin >> K;

	for(int i = 0; i < N; i++)
	{
		fin >> A[i];
	}

	fin.close();
}


void afisare()
{
	fstream fout(outfile, ios::out);

	fout << ResultStart << " ";
	fout << ResultEnd << " ";
	fout << Result << "\n";

	fout.close();
}


void solve()
{
	deque<int> removables;
	int removableSum = 0;

	deque<int> deck;
	int best = 0;
	int bStart = 0;
	int bEnd = K-1;

	int start = 0;
	int end = K-1;
	int current = 0;

	for(int i = 0; i < K; i++)
	{
		deck.push_back(A[i]);
		current += A[i];
	}

	best = current;

	for(int i = K; i < N; i++)
	{

		int max1 = current + A[i];
		int max2 = current + A[i] - A[start];

		current = max(max1, max2);

		if(current == max2)
		{
			deck.push_back(A[i]);
			deck.pop_front();
			end++;
			start++;
			
		}
		else
		{
			removables.push_back(deck.front());
			removableSum += deck.front();
			deck.pop_front();
			deck.push_back(A[i]);
			end++;
		}

		while(removables.size() > 0 && removableSum < 0)
		{
			start++;
			removableSum -= removables.front();
			current -= removables.front();
			removables.pop_front();
		}

		
		if(current > best)
		{
			best = current;
			bStart = start;
			bEnd = end;
		}

	}

	Result = best;
	ResultStart = bStart + 1;
	ResultEnd = bEnd + 1;


}


int main()
{
	citire();
	solve();
	afisare();

}