Cod sursa(job #615249)

Utilizator skyelHighScore skyel Data 9 octombrie 2011 01:54:04
Problema Secventa Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUFSIZE 3000000
#define input "secventa.in"
#define output "secventa.out"

int main()
{
    char *buffer;
    int *array,*position;
    int n,k,i,begin,end,max,maxp;
    freopen(input, "r",stdin);
    freopen(output, "w",stdout);
    scanf("%d",&n);
    scanf("%d",&k);
    array = malloc(sizeof(int) * n);
    position = malloc(sizeof(int) * n);
    memset(position,0,sizeof(int)*n);
    buffer = malloc(sizeof(char) * BUFSIZE);
    fgets(buffer,BUFSIZE,stdin);
    fgets(buffer,BUFSIZE,stdin);
    for (i = 0; i < n; ++i)
    {
        sscanf(buffer,"%d",&array[i]);
        while(*buffer != ' ') buffer++;
        buffer++;
    }
    begin = 1;
    end = 0;
    max = -30000;
    maxp = 0;
    for (i = 0; i < n; ++i)
    {
        while (array[i] < array[position[end]] && end >= begin) end--;
        while (end >= begin && ((i - position[begin]) >= k)) begin++;
        
        position[++end] = i;
        if(i >= (k-1) && max < array[position[begin]])
        {
            max = array[position[begin]];
            maxp = i;
        }
    }
    maxp++;
    printf("%d %d %d\n",maxp - k + 1, maxp, max);
    return 0;
}