Cod sursa(job #1552120)

Utilizator Emy1337Micu Emerson Emy1337 Data 17 decembrie 2015 11:44:34
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");

const int MAXN = 500100;


int values[MAXN];
deque< int > d;
int miny=-10000000,miny2,poz;
void insert(int poz)
{
    while (!d.empty() && values[d.back()] > values[poz])
        d.pop_back();
    d.push_back(poz);

}

int get_min(int curIndex)
{
    while(!d.empty() && d.front() < curIndex)
        d.pop_front();
    return values[d.front()];
}

int n,k;

int main()
{
    fin>>n>>k;
    for (int i = 1; i <= n; ++i)
        fin >> values[i];

    for (int i = 1; i <= k; ++i)
        insert(i);

    long long sum = 0;

    for (int i = k + 1; i <= n + 1; ++i)
    {
        miny2=get_min(i - k);
        if(miny < miny2)
        {
            miny= miny2;
            poz= i-k;
        }

        insert(i);
    }
    fout<<poz<<" "<<poz+k-1<<" "<<miny;
}