Cod sursa(job #1290603)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 11 decembrie 2014 15:43:39
Problema Secventa Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>
#define MAXN 500000
#define MAXV 30000
int st, dr, k, n, v[MAXN+1], d[MAXN+1];
void stanga(int i){
    if(i-d[st]==k){
        st++;
    }
}
void dreapta(int i){
    while((st<=dr)&&(v[i]<=v[d[dr]])){
        dr--;
    }
}
int main(){
    int i, max=-MAXV-1, outdr, semn;
    char ch;
    FILE *fin, *fout;
    fin=fopen("secventa.in", "r");
    fout=fopen("secventa.out", "w");
    fscanf(fin, "%d%d ", &n, &k);
    for(i=1; i<=n; i++){
        ch=fgetc(fin);
        if(ch=='-'){
            semn=-1;
            ch=fgetc(fin);
        }else{
            semn=1;
        }
        while((ch>='0')&&(ch<='9')){
            v[i]*=10;
            v[i]+=ch-'0';
            ch=fgetc(fin);
        }
        v[i]*=semn;
    }
    for(i=1; i<=n; i++){
        stanga(i);
        dreapta(i);
        dr++;
        d[dr]=i;
        if((i>=k)&&(v[d[st]]>max)){
            max=v[d[st]];
            outdr=i;
        }
    }
    fprintf(fout, "%d %d %d\n", outdr-k+1, outdr, max);
    return 0;
}