Cod sursa(job #718175)

Utilizator alexa_mihaltanMihaltan Alexandra alexa_mihaltan Data 20 martie 2012 16:38:50
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
#include <iostream>
#include <iomanip>
#define dim 500001
using namespace std;

int n,k,poz=0,min,baza,pozinit,pozfin,a[dim];

void citire()
{
	int i;
	ifstream f1;
	f1.open("secventa.in");
	f1>>n;
	f1>>k;
	for(i=1;i<=n;i++)
	{
		f1>>a[i];
	}
	f1.close();
}

void scriere()
{
	ofstream f2;
	f2.open("secventa.out");
	f2<<pozinit<<" "<<pozfin<<" "<<baza;
	f2.close();
}

void prelucrare()
{
	int i,st=1,dr=1;
	int deque[dim];
	baza=-999999999;
	deque[1]=1;
	for(i=2;i<=n;i++)
	{
		while ((a[deque[st]]>=a[i])and(dr>=st))
					dr--;
		dr++;
		deque[dr]=i;
		if (a[deque[st]]>baza)
		{
			baza=a[deque[st]];
			pozinit=i+1-k;
			pozfin=i;
		}
		if (deque[st]<i+2-k)
			st++;
	}
}


int main()
{
	citire();
	prelucrare();
	scriere();
	return 0;
}