Cod sursa(job #894542)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 26 februarie 2013 21:54:14
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <deque>
#define INF 2000000000

using namespace std;

int n, k, a[500010], start, finish, baza = -INF;
deque <int> d;

int main()
{
    ifstream f ("secventa.in");
    f>>n>>k;
    int i;
    for (i=1; i<=n; i++)
    {
        f>>a[i];
        while (!d.empty() && a[i] <= a[d.back()])
        {
            d.pop_back();
        }
        d.push_back(i);

        if (d.front () == i-k)
            d.pop_front();

        if (i>=k)
        {
            if (a[d.front()] > baza)
            {
                baza = a[d.front()];
                start = i-k+1;
                finish = i;
            }
        }
    }
    f.close();

   // while (start > 1 && a[start-1] >= baza)
   //     start--;

    ofstream g("secventa.out");
    g<<start<<" "<<finish<<" "<<baza<<"\n";
    g.close();


    return 0;
}