Cod sursa(job #3000307)

Utilizator DomnulMilandruMilandru Nicon-David DomnulMilandru Data 12 martie 2023 12:04:47
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb

#include <fstream>
#include <deque>
using namespace std;
ifstream cin("sum2.in");
ofstream cout("sum2.out");
int sume[100001];
int n,l,u,x;
deque<int> M;
int main()
{
    cin>>n>>l>>u;
    int k=u-l+1;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        sume[i]=sume[i-1]+x;
    }
    int maxi=-200000000;
    for(int i=1;i<k;i++)
    {
        while(!M.empty() && sume[M.back()]>=sume[i])
           M.pop_back();
        M.push_back(i);
    }
    for(int i=k;i+u-1<=n;i++)
    {
        while(!M.empty() && sume[M.back()]>=sume[i])
           M.pop_back();
        M.push_back(i);
        if(M.front()<=i-k)
         M.pop_front();
        int suma=sume[i+u-1]-sume[M.front()];
        maxi=max(suma,maxi);
    }
    cout<<maxi;
    return 0;
}