Cod sursa(job #1987319)

Utilizator OlivianOlivian Dan Cretu Olivian Data 30 mai 2017 12:26:03
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<cstdio>
#include<deque>
#include <algorithm>
const long long inf=1e15;
using namespace std;
int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    int n,l,u,v[500007];
    long long s[500007];
    long long maxi=-inf;
    deque<int> dq;
    s[0]=0;
    scanf("%d%d",&n,&l);
    for(int i=1;i<=n;i++) {scanf("%d",&v[i]);s[i]=s[i-1]+v[i];}
    for(int i=l;i<=n;i++)
    {
        while(!dq.empty() && s[i-l]<=s[dq.back()]) dq.pop_back();
        dq.push_back(i-l);
        if(dq.front()<i-n) dq.pop_front();
        maxi=max(maxi,s[i]-s[dq.front()]);
    }
    printf("%lld",maxi);

}