Cod sursa(job #1794825)

Utilizator tanasaradutanasaradu tanasaradu Data 1 noiembrie 2016 19:14:40
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
deque<int>maxim;
deque<int>minim;
int a[50005],sum[50005],n,k;
void Citire()
{
    int i;
    fin>>n>>k;
    for(i=1;i<=n;i++)
        fin>>a[i];
    fin.close();
}
void Rezolvare()
{
    int i,smaxim=-10000000,ind,ind1,x;
    sum[1]=a[1];
    for(i=2;i<=n;i++)
        sum[i]=sum[i-1]+a[i];
    for(i=1;i<=n;i++)
    {
        x=sum[i];
        while(!maxim.empty() and sum[maxim.back()]<x)
            maxim.pop_back();
         while(!minim.empty() and sum[minim.back()]>x)
            minim.pop_back();
        maxim.push_back(i);
        minim.push_back(i);
        if(abs(maxim.front()-minim.front())<k)
            maxim.pop_front();
        if(!maxim.empty() and !minim.empty() and sum[maxim.front()]-sum[minim.front()]>smaxim)
        {
            smaxim=sum[maxim.front()]-sum[minim.front()];
            ind=minim.front()+1;
            ind1=maxim.front();
        }
    }
    fout<<ind<<" "<<ind1<<" "<<smaxim<<"\n";
}
int main()
{
    Citire();
    Rezolvare();
    return 0;
}