Cod sursa(job #664320)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 19 ianuarie 2012 22:04:23
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.56 kb
#include<fstream>
#define NMAx 500100
using namespace std;
short n,k,deque[NMAx],v[NMAx],scos[NMAx],sol;

int main() {
	int i,l,r,tmp;
	ifstream in("secventa.in");
	ofstream out("secventa.out");
	in>>n>>k;
	v[0]=-30010;
	for(i=1,l=1,r=0;i<=n;i++) {
		in>>v[i];
		while(l<r&&v[i]<v[deque[r]])
			r--;
		tmp=deque[r+1];
		deque[++r]=i;
		if(tmp)
			scos[i]=deque[r]-tmp+scos[tmp];
		if(deque[l]==i-k)
			l++;
		if(i>=k&&v[sol]<v[deque[l]])
			sol=deque[l];
		}
	out<<sol-k+1<<' '<<sol<<' '<<v[sol]<<'\n';
	in.close();
	out.close();
	return 0;
}