Cod sursa(job #967155)

Utilizator sorin2kSorin Nutu sorin2k Data 27 iunie 2013 11:39:12
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<iostream>
#include<fstream>
#include<deque>
using namespace std;

struct Nod {
	int val, poz;
};

ifstream fin("secv2.in");
ofstream fout("secv2.out");
int a[50001], n, k, i, sume[50001], start, end, startaux;
long long rez;
deque<Nod> d;

void citire()
{
	fin >> n >> k;
	for(i = 1; i <= n; i++)
	{
		fin >> a[i];
	}
}

void calcul_sume_partiale()
{
	sume[0] = 0;
	sume[1] = a[1];
	for(i = 2; i <= n; i++)
	{
		sume[i] = sume[i-1] + a[i];
	}
}

Nod make_nod(int val, int poz)
{
	Nod p;
	p.val = val;
	p.poz = poz;
	return p;
}

int main()
{
	citire();
	calcul_sume_partiale();
	start = 0;
	end = k;
	rez = sume[k];
	d.push_back(make_nod(0, 0));
	for(i = k + 1; i <= n; i++)
	{
		while(!d.empty() && sume[i-k] < d.back().val)
		{
			d.pop_back();
		}
		d.push_back(make_nod(sume[i-k], i-k));
		if(sume[i] - sume[d.front().poz] > rez)
		{
			rez = sume[i] - sume[d.front().poz];
			start = d.front().poz + 1;
			end = i;
		}
	}
	fout << start << " " << end << " " << rez;
	return 0;
}