Cod sursa(job #1274918)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 24 noiembrie 2014 16:10:51
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <stdio.h>
#define MAX -30000
FILE *fin, *fout;
int n, k, *v, dr = 0, st = 1, p1, p2, max = MAX;
struct deq
{
       int val;
       int poz;
} *d;
int main()
{
    fin = fopen("secventa.in", "r");
    fout = fopen("secventa.out", "w");
    fscanf(fin, "%d%d", &n, &k);
    v = new int[n];
    d = new deq[n*2];
    for(int i =0; i< n; i++) fscanf(fin, "%d", &v[i]);
    for(int i = 0; i< k - 1; i++)
    {
            if(dr == 0)
            {
                  dr++;
                  d[dr].val = v[i];
                  d[dr].poz = i;
                  continue;
            }
            while(v[i] <= d[dr].val && dr > st)
            {
                 dr--;
            }
            dr++;
            d[dr].val = v[i];
            d[dr].poz = i;
    }
    for(int i = k-1; i< n; i++)
    {
            while(v[i] <= d[dr].val && dr > st)
            {
                 dr--;
            }
            dr++;
            d[dr].val = v[i];
            d[dr].poz = i;
            while(d[st].poz <= d[dr].poz - k+1)
            {
                         if(d[st].val > max)
                         {
                                      max = d[st].val;
                                      p1 = d[st].poz+1;
                                      p2 = d[dr].poz+1;
                         }
                         st++;
            }
    }
    fprintf(fout, "%d %d %d\n", p1, p2, max);
    fclose(fin);
    fclose(fout);
    return 0;
}