Cod sursa(job #1538535)

Utilizator Vele_GeorgeVele George Vele_George Data 29 noiembrie 2015 12:33:51
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <iostream>
#include <cstdio>
#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()
{
    FILE *f, *g;

    f = fopen("secventa.in", "r");
    g = fopen("secventa.out", "w");

    fscanf(f, "%d%d", &n, &k);

    v.resize(n+1);
    for(int i=1; i<k; i++)
    {
        fscanf(f, "%d", &v[i]);
        ins(i);
    }
    for(int i=k; i<=n; i++)
    {
        fscanf(f, "%d", &v[i]);
        ins(i);
        if (v[deq.front()] > mx)
        {
            mx = v[deq.front()];
            p = i;

        }
    }

    fprintf(g, "%d %d %d", p-k+1, p, mx);

    return 0;
}