Cod sursa(job #2062391)

Utilizator CroitoruAlinCroitoru Alin CroitoruAlin Data 10 noiembrie 2017 12:20:11
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
char aux[3500002];
int main()
{
    ifstream fin("secventa.in");
   int n,k;
   int *v;
    int i,lg,semn,nr;
    fin>>n>>k;
    v=new int[n+1];
    fin.get();
    fin.getline(aux,3500002);

    semn=lg=1;
    for(i=0;aux[i]!=0;)
    {
        if('0'<=aux[i] && aux[i]<='9')
        {
            nr=0;
            while('0'<=aux[i] && aux[i]<='9')
            {
                nr=nr*10+aux[i]-'0';
                i++;
            }
            nr*=semn;
            semn=1;

            v[lg]=nr;
            lg++;
        }
        else if(aux[i]=='-')
        {
            i++;
            semn=-1;
        }
        else i++;
    }
    deque<int> d;
    int sol=-31000;
    int prim,ultim;
    for(i=1;i<=n;i++){
        for(;!d.empty() && v[i]<=v[d.front()];)
            d.pop_front();
        d.push_front(i);
        while(!d.empty() && i-k>=d.back())
            d.pop_back();
        if(k<=i && v[d.back()]>sol)
        {
            sol=v[d.back()];
            prim=i-k+1;
            ultim=i;
        }
    }
    ofstream fout("secventa.out");
    fout<<prim<<" "<<ultim<<" "<<sol;
    fout.close();
    delete[] v;
    return 0;
}