Cod sursa(job #710375)

Utilizator nalexandruIovan Alexandru Nicolae nalexandru Data 9 martie 2012 15:43:22
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<fstream>
#define NMax 500001
using namespace std;

fstream fin("secventa.in",ios::in);
fstream fout("secventa.out",ios::out);

int a[NMax],n,k;
int solIn,solMinim;

int calcMinim(int poz1,int poz2)
{
	int min=a[poz1];
	for(int i=poz1+1;i<=poz2;i++)
		if(a[i]<min)
			min=a[i];
	return min;
}

void Citeste()
{
	fin>>n>>k;
	for(int i=0;i<n;i++)
		fin>>a[i];
}

void Rezolva()
{
	solIn=0;
	solMinim=calcMinim(solIn,solIn+k-1);
	int curentIn=0,curentMin=solMinim;
	for(int i=0;i<n-k;i++)
	{
		if(a[i+k]<curentMin&&(i+k+1)+k-1<n)
		{
			curentIn=i+k+1;
			curentMin=calcMinim(curentIn,curentIn+k-1);
			if(solMinim<curentMin){ solMinim=curentMin; solIn=curentIn;}
			i=i+k;
		}
		else
		{
			if(a[i]==curentMin)
			{
				curentIn++; curentMin=calcMinim(curentIn,curentIn+k-1);
				if(solMinim<curentMin){ solMinim=curentMin; solIn=curentIn; }
			}
			else
			{
				curentIn++;
			}
		}
	}
}

void Tipareste()
{
	fout<<solIn+1<<" "<<solIn+k<<" "<<solMinim;
}

int main()
{
	Citeste();
	Rezolva();
	Tipareste();
}