Mai intai trebuie sa te autentifici.

Cod sursa(job #27447)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 6 martie 2007 14:19:20
Problema Secventa Scor 20
Compilator c Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<stdio.h>
#define NMAX 500010
#define INF 666666
#define PMAX 60666

int V[NMAX], D[NMAX], N, K, Max = -INF, PF;
int P[PMAX];

int main()
{
        int i, st = 0, sf = 1, j, min;

        freopen("secventa.in", "r", stdin);
        scanf("%d %d", &N, &K);
        for (i = 1; i <= N; i++) scanf("%d", V+i);

        min = INF;
        for (i = 0; i < NMAX; i++) D[i] = INF;
        sf = 0;
        for (i = 1; i <= K; i++)
        {
                for (;sf >= st && D[sf] > V[i]; sf--);
                D[++sf] = V[i];
                P[sf] = i;
        }
        Max = D[1]; PF = K;

        st = 1;
        for (i = K+1; i <= N; i++)
        {
                st = ((P[st] < i-K+1) ? (st+1):st);
                for (;sf >= st && D[sf] > V[i]; sf--);
                D[++sf] = V[i];
                P[sf] = i;
                if (Max < D[st]) Max = D[st], PF = i;
        }

        freopen("secventa.out", "w", stdout);
        printf("%d %d %d\n", PF-K+1, PF, Max);

        return 0;
        
}