Cod sursa(job #29619)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 9 martie 2007 17:47:31
Problema Secventa Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define NMAX 500010
#define INF 666666
#define FOR(i, a, b) for (i = a; i <= b; i++)
#define FOR2(i, a, b, c) for(;i >= a && b > c;i--);

int V[NMAX], D[NMAX], N, K, Max = -INF, PF;
int P[NMAX];
char buf[6*NMAX];

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

        FILE *fin = fopen("secventa.in", "r");
        fscanf(fin, "%d %d ", &N, &K);
        fgets(buf, sizeof(buf), fin);
        n = strlen(buf);
        N = 0;
        for (i = 0; i < n; i++)
            if ('0' <= buf[i] && buf[i] <= '9') a = a*10+buf[i]-'0';
            else
                if (buf[i] == ' ') V[++N] = a, a = 0;
        V[++N] = a;

        min = INF;
        FOR(i, 0, N) D[i] = INF;
        sf = 0;
	FOR(i, 1, K)        
        {
                FOR2(sf,1,D[sf],V[i]);
                D[++sf] = V[i];
                P[sf] = i;
        }
        Max = D[1]; PF = K;

        st = 1;
        FOR(i, K+1, N)
        {
                if (P[st] < i-K+1) st++;
                FOR2(sf, st, D[sf], V[i])
                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;
        
}