Cod sursa(job #1329693)

Utilizator Vele_GeorgeVele George Vele_George Data 29 ianuarie 2015 19:37:25
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#define inf (1<<30)

using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");

vector<int> v;
deque<int > deq;
int n, k, mx=-inf,st,dr;


void verificare()
{
    if (v[deq.front()]>mx)
    {
        mx=v[deq.front()];
        dr=deq.front();
        st=dr-k+1;
    }
}


void ins(int x)
{
    while(!deq.empty() && v[deq.back()] > v[x])
        deq.pop_back();
    deq.push_back(x);

}

//ATTEKNTJXE


int main()
{
    f >> n >> k;
    v.resize(n+1);
    for(int i=1; i<k; i++)
    {
        f >> v[i];
        ins(i);
    }

    for(int i=k; i<=n; i++)
    {
        f >> v[i];
        if (deq.front() <= i-k) deq.pop_front();
        ins(i);
        verificare();
    }

    g << st << " " << dr << " " << mx;


    return 0;
}