Cod sursa(job #423402)

Utilizator erzsikeRusz Elisabeta erzsike Data 23 martie 2010 20:41:47
Problema Secventa Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<fstream> 
#include<iostream> 
using namespace std; 
long i,n,t[5000002],s,d,k,c[5000002],e,v,cds,maxi; 


int main() 
{ 
	ifstream f("secventa.in"); 
	ofstream  g("secventa.out"); 
	f>>n>>k; 
	for(i=1;i<=n;i++) 
		f>>t[i]; 
	s=1;
	d=1; 
	c[d]=1; 
	for(i=2;i<k;i++) 
	{ 
		while(t[i]<=t[c[d]]  &&  d>=s)
			d--; 
		c[++d]=i; 
	} 
	maxi=t[c[s]]; 
	e=1; 
	v=k; 
	for (i=k;i<=n;i++) 
	{ 
		cds=c[s]; 
		while(c[s]+k<=i)
			s++;	
		while(t[i]<=t[c[d]] && d>=s)
			d--; 
		c[++d]=i; 
		if(cds!=c[s]) 
				if(t[c[s]]>maxi) 
				{ 
					maxi=t[c[s]]; 
					v=i; 
					e=i-k+1;	
				}            
	} 
	g<<e<<' '<<v<<' '<<maxi; 
	return 0;
}