Cod sursa(job #56988)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 30 aprilie 2007 21:08:24
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<stdio.h>
#define MAXN 1000001
#define INF 1000000000

int pA,pB,REZ,N,U,L,V[MAXN],deque[MAXN];
int poz[MAXN],X[MAXN],query[MAXN];

void citesteDate(){
     int i;
     freopen("secv2.in","r",stdin);
     scanf("%d %d",&N,&L);
     U=N;
     for(i=1;i<=N;i++) scanf("%d ",&V[i]);
}

void proceseaza(){
     int i,j,s1,s2;
     for (s1=1,s2=1,i=1;i<=N;i++){
         X[i]=X[i-1]+V[i];
         while (s1<=s2 && deque[s2]>X[i])s2--;
         s2++;
         deque[s2]=X[i];
         poz[s2]=i;
         while (s1<=s2 && poz[s1]+U-L<i) s1++;
         query[i]=poz[s1];
    }
    REZ=-INF;
    for (i=L;i<=N;i++){
        j=query[i-L];
        if (X[i]-X[j]>REZ){
           REZ=X[i]-X[j];pA=j+1;pB=i;
        }
    }
}

void afiseazaRez(){
     freopen("secv2.out","w",stdout);
     printf("%d %d %d\n",pA,pB,REZ);
}

int main()
{
 citesteDate();
 proceseaza();
 afiseazaRez();
 return 0;
}