Cod sursa(job #809391)

Utilizator cdascaluDascalu Cristian cdascalu Data 8 noiembrie 2012 11:22:27
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<stdio.h>
#define Nmax 500001
#define INF 0x3f3f3f
int N,K,v[Nmax],d[2][Nmax];
int main()
{
	FILE*f = fopen("secventa.in","r");
	fscanf(f,"%d%d",&N,&K);
	for(int i=1;i<=N;++i)
		fscanf(f,"%d",&v[i]);
	
	int st=1,fn=0,sol,sol_left,sol_right;
	sol = -INF;
	for(int i=1;i<=N;++i)
	{
		while(fn>st && d[0][fn] >= v[i])
			--fn;
		++fn;
		d[0][fn] = v[i];
		d[1][fn] = i;
		
		while( i - d[1][st] + 1 >= K)
		{
			if(d[0][st] > sol)
			{
				sol = d[0][st];
				sol_left = d[1][st];
				sol_right = i;
			}
			++st;
		}
	}
	FILE*g = fopen("secventa.out","w");
	fprintf(g,"%d %d %d\n", sol_left, sol_right, sol);
	fclose(g);
	return 0;
}