Cod sursa(job #1334263)

Utilizator akaprosAna Kapros akapros Data 4 februarie 2015 09:46:36
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
#define Nmax 50005
using namespace std;
int v[Nmax],s[Nmax];
int n,i,j,m,k,sol,p,q;
deque < int >e;
int main()
{
    freopen("secv2.in","r",stdin);
    freopen("secv2.out","w",stdout);
    scanf("%d %d",&n,&k); sol=-1000000000;
    for (i=1;i<=n;i++) scanf("%d",&v[i]);
    for (i=n;i>=1;i--)
    {
        s[i]=s[i+1]+v[i];
        if (i<k) continue;
        while ((!e.empty())&&(s[e.back()]>s[i])) e.pop_back();
        e.push_back(i);
    }
    for (i=1;i<=n;i++)
    {
        while (!e.empty() && e.front()-i<k)
        e.pop_front();
        if (e.empty()) continue;
        if (s[e.front()]>0)
        {
            if (s[i]>sol)
            sol=s[i],p=i,q=n;
            continue;
        }
        if (s[i]-s[e.front()]>sol)
        sol=s[i]-s[e.front()],p=i,q=e.front()-1;
    }
    printf("%d %d %d",p,q,sol);
    return 0;
}