Cod sursa(job #35272)

Utilizator lucibitLucian Onea lucibit Data 21 martie 2007 22:46:54
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include<stdio.h>
#define N 50001
long v[N],q[N],poz[N];
long n,k,p1,p2;
long max,S[N],deque[N];
void citeste()
{long i,j;
 freopen("secv2.in","r",stdin);
 scanf("%d %d\n",&n,&k);
 for(i=1;i<=n;i++) scanf("%d ",&v[i]);
  }
void solve()
{long j,i,cap,coada;
 for(cap=1,coada=1,i=1;i<=n;i++)
 {S[i]=S[i-1]+v[i];
	while (cap<=coada && deque[coada]>S[i]) coada--;
	deque[++coada]=S[i];
	poz[coada]=i;

	while (cap<=coada && poz[cap]+k<=i) cap++;
	q[i]=poz[cap];
	}
  max=-10000000;
 for(i=k;i<=n;i++)
  {j=q[i-k];
	  if(S[i]-S[j]>max){max=S[i]-S[j]; p1=j+1; p2=i;}
	}
 }

int main()
{
 citeste();
 deque[1]=2500001;
 solve();
 freopen("secv2.out","w",stdout);
 printf("%d %d %ld\n",p1,p2,max);
 return 0;
 }