Cod sursa(job #1533374)

Utilizator raulmuresanRaul Muresan raulmuresan Data 22 noiembrie 2015 14:36:44
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<fstream>
#include<deque>
#include<string>

using namespace std;
int i,n,j,k,cont,ok,maxi,x,y,poz;
 int a[500100];
 int sum;
deque<int> d;
string s;


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

void parsare()
{
    int i,l,x;
    getline(fin,s);
    getline(fin,s);
    j=0;x=0;l=s.length();
    for(i=1;i<=n;i++)
    {
        x=0;ok=1;
        if(s[j]==' ')
        {
            j++;
        }
        if(s[j]=='-')
        {
            ok=-1;
            j++;
        }
         while(s[j]!=' ' and j<l)
        {
            x=(x*10)+s[j]-'0';
            j++;

        }
        j++;
        a[i]=x*ok;
    }
}

int main()
{
    fin>>n>>k;
    sum=-1000000000;
    parsare();
    for (i=1;i<=n;i++)
    {
        while (!d.empty() && a[d.back()]>=a[i]) d.pop_back();
        d.push_back(i);
        if (i-k==d.front()) d.pop_front();
       if (i>=k && a[d.front()]>sum)
        {
         poz=i;
         sum=a[d.front()];
        }
    }
    fout<<poz-k+1<<" "<<poz<<" "<<sum;

}