Cod sursa(job #1538528)

Utilizator Vele_GeorgeVele George Vele_George Data 29 noiembrie 2015 12:05:13
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#define inf (1<<30)
using namespace std;

deque<int> deq;
vector<int> v;
int n, k, x, y, p, mx=-inf;

void ins(int x)
{
    if (!deq.empty() && deq.front() < x-k+1)
    {
        deq.pop_front();
    }
    while(!deq.empty() && v[deq.back()] >= v[x])
    {
        deq.pop_back();
    }
    deq.push_back(x);

    return;
}

int main()
{
    ifstream f("secventa.in");
    ofstream g("secventa.out");
    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];
        ins(i);
        if (v[deq.front()] > mx)
        {
            mx = v[deq.front()];
            p = i;

        }
    }

    g << p-k+1 << " " << p << " " << mx;

    f.close();
    g.close();
    return 0;
}