Cod sursa(job #3159576)

Utilizator Cezar2009Cezar Mihai Titihazan Cezar2009 Data 21 octombrie 2023 17:03:14
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
//https://www.infoarena.ro/problema/secventa
#include <bits/stdc++.h>
using namespace std;

ifstream fin ("secventa.in");
ofstream fout ("secventa.out");

int main()
{
    int n,i,x,k;
    int max=-40000,maxin=0,maxsf=0;
    deque <pair<int,int>> dq;
    fin>>n>>k;
    fin>>x;
    dq.emplace_back(0,x);
    for(i=1;i<n;i++)
    {
        fin>>x;
        while((dq.empty()==false)&&(x<dq.back().second))
        {
            dq.pop_back();
        }

        dq.emplace_back(i,x);

        if(i>=(k-1))
        {
            while((dq.empty()==false)&&(dq.front().first<=(i-k)))
            {
                dq.pop_front();
            }
            //cout<<dq.front().second<<"\n";
            if(dq.empty()==false)
            {
                if(max<dq.front().second)
                {
                    max=dq.front().second;
                    //if()
                    //cout<<"bun "<<i<<"\n";
                    maxsf=i+1;
                    maxin=i-k+2;
                }
            }
        }

    }
//    cout<<dq.front().second<<"\n";
//    sum+=(long long)dq.front().second;
    //return 0;
//    for(auto &x : dq)
//    {
//        cout<<x.first<<" "<<x.second<<"\n";
//    }
    fout<<maxin<<" "<<maxsf<<" "<<max;
    return 0;
}