Cod sursa(job #205445)

Utilizator moga_florianFlorian MOGA moga_florian Data 31 august 2008 19:35:22
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<stdio.h>
#define Nmax 50005

int A[Nmax], S[Nmax];
int dq[Nmax], li,lf,pozli,pozlf;

int main(){

    FILE *fin = fopen("secv2.in","r"),
         *fout = fopen("secv2.out","w");
         
    int N, K;
    fscanf(fin,"%d%d",&N,&K);
    
    for(int i=1;i<=N;i++)
        fscanf(fin,"%d",&A[i]);    
    
    for(int i=1;i<=N;i++)
        S[i] = S[i-1] + A[i];
        
    li=1;
    lf=0;
    
    int sol = -30000;
    for(int i=K;i<=N;i++){
    
        int j=i-K;
        while(lf>=li && S[dq[lf]] > S[j]) 
             lf--;
        dq[++lf] = j;
            
        /*
        if(dq[li] < i-limita_maxima)
            li++;
        */
        
        if(S[i] - S[dq[li]] > sol)
            sol = S[i]-S[dq[li]], pozli=dq[li]+1, pozlf=i;
    }
    
    fprintf(fout,"%d %d %d\n",pozli,pozlf,sol);
    
    fclose(fin);
    fclose(fout);
    return 0;
    
}