Cod sursa(job #2120970)

Utilizator thedorbulacovschittrter thedorbulacovschi Data 3 februarie 2018 10:30:55
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.in");
int n,k,i,a,v[50005],inc,st,dr;
long long sum[50005],best,s2,s;
int main()
{
    fin>>n>>k;
    for(i=1;i<=n;i++)
    {
        fin>>a;
        sum[i]=sum[i-1]+a;
    }
    best=sum[k];
    v[1]=1;
    v[0]=1;
    for(i=k+1;i<=n;i++)
    {
        inc=i-k+1;
        s=sum[i]-sum[inc-1];
        while(v[0]!=0 && s>=sum[i]-sum[v[v[0]]-1])
            v[0]--;
        v[++v[0]]=inc;
        if(best<sum[i]-sum[v[1]-1])
        {
            best=sum[i]-sum[v[1]-1];
            st=v[1];
            dr=i;
        }
    }
    fout<<st<<" "<<dr<<" "<<best<<'\n';
    return 0;
}