Cod sursa(job #2670021)

Utilizator metallidethantralayerIon Cojocaru metallidethantralayer Data 8 noiembrie 2020 18:33:41
Problema Secventa 2 Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.59 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("secv2.in");
ofstream g("secv2.out");
int64_t v[50005],ans=-1e16,n,k,i1,j;
deque <int> Q;
int main()
{
    f>>n>>k;
    for(int i=1; i<=n; i++)
        f>>v[i],v[i]+=v[i-1];
    for(int i=1; i<=n; i++)
    {
        if(i<=k)
            continue;
        while(!Q.empty()&&v[Q.back()]>=v[i-k])
            Q.pop_back();
        Q.push_back(i-k);
        if(Q[0]<i-n)
            Q.pop_front();
        if(ans<v[i]-v[Q[0]])
            i1=Q[0]+1,j=i,ans=v[i]-v[Q[0]];
    }
    g<<i1<<' '<<j<<' '<<ans;

    return 0;
}