Cod sursa(job #1139325)

Utilizator omerOmer Cerrahoglu omer Data 11 martie 2014 00:09:04
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <iostream>
#include<stdio.h>
using namespace std;
FILE *f,*g;
int k,begi,en;
int front(int a[])
    {
        return a[begi];
    }
void popfront(int a[])
    {
        if (begi<en) begi++;
    }
void push(int a[],int b)
    {
        a[en++]=b;

    }
void popback(int a[])
    {
        if (begi<en) en--;
    }
bool empty(int a[])
    {
        if (begi==en) return 1; else return 0;
    }
void add(int a[],int x[],int b)
    {

        while(!empty(a)&&x[a[en-1]]>x[b]) popback(a);
        push(a,b);
    }
int betteradd(int a[],int x[],int b)
    {
        int q=a[begi];
        if (q==b-k) popfront(a);
        add(a,x,b);
        return q;
    }



int mini[500001];
int val[500001],n,i;
int main()
{

    int minim=-100000000,init=0,s;
    f=fopen("secventa.in","r");
    g=fopen("secventa.out","w");
    fscanf(f,"%d%d",&n,&k);
    for(i=1;i<=n;i++) fscanf(f,"%d",&val[i]);
    for(i=1;i<=k;i++) add(mini,val,i);
    for(i=k+1;i<=n;i++)
        {
          s=betteradd(mini,val,i);
          if (minim<val[s]) {minim=val[s];init=i-k;}
        }
    if (minim<val[mini[begi]]) {minim=val[mini[begi]];init=n-k+1;}
    fprintf(g,"%d %d %d",init,init+k-1,minim);
















    return 0;
}