Cod sursa(job #2321040)

Utilizator AlexandruPaulSirbu Alex AlexandruPaul Data 15 ianuarie 2019 17:05:58
Problema Arbori indexati binar Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
const int Maxx=1e5+3;
const int INF=(1<<30);
deque <int> Q;
ifstream fin("sum2.in");
ofstream fout("sum2.out");
int n,l,u;
int i,ans=-INF;
int A[Maxx];
int main() {
    fin>>n>>l>>u;
    for (i=1;i<=n;++i){
        fin>>A[i];
        A[i]+=A[i-1];
    }
    Q.push_back(0);
    for (i=1;i<=n-l;++i){
        while (!Q.empty() && A[i]<=A[Q.back()]){
            Q.pop_back();
        }
        Q.push_back(i);
        while (!Q.empty() && Q.front()<i+l-u) Q.pop_front();
        if (i>=l){
            ans=max(ans,A[i+l]-A[Q.front()]);
        }
    }
    fout<<ans;
    return 0;
}