Cod sursa(job #137092)

Utilizator alex_dincaDinca Alexandru-Nicolae - UPB alex_dinca Data 16 februarie 2008 21:32:52
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <stdio.h>   
#include <string.h>   
#include <stdlib.h>   
#define nmax 500004   
  
int N, K, i, A[nmax], bottom, top, ult, V[nmax], P[nmax], max, aaa, bbb, l, nr=1;
  
char S[nmax<<3];   
  
int main(){   
    max = -2000000000;                   
    freopen("secventa.in", "r", stdin);   
    freopen("secventa.out", "w", stdout);
    scanf("%d %d\n", &N, &K);              
    gets(S);                               
    A[1] = atoi(strtok(S, " \n"));         
    for (i = 2; i <= N; i++)   
        A[i] = atoi(strtok(NULL, " \n"));  
    for (i = 1, bottom = 0, top = -1, ult = 0; i <= N - K + 1; i++){   
        while (ult < i + K - 1 && ult < N) {   
            ult++;                           
            while (top >= bottom && V[top] >= A[ult])   
                top--;                       
            top++;                           
            V[top] = A[ult];   
            P[top] = ult;   
        }                                    
        while (P[bottom] < i)   
            bottom++;                        
        if (V[bottom] > max){   
            max = V[bottom];   
            aaa = i;   
            bbb = i+K-1;      
        }                     
    }                         
    printf("%d %d %d\n", aaa, bbb, max);  
    return 0;   
}