Cod sursa(job #2124354)

Utilizator darisavuSavu Daria darisavu Data 7 februarie 2018 09:46:52
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <fstream>
#include <queue>
using namespace std;
ifstream f("secv2.in");
ofstream g("secv2.out");
queue<int> c;
int n,k,v[50005],i,s,best,st,dr,x,sum;
int main()
{
    f>>n>>k;
    for(i=1;i<=n;i++)
    {
        f>>x;
        v[i]=v[i-1]+x;
    }
    best=v[k];
    st=1;
    dr=k;
    c.push(1);
    for(i=k+1;i<=n;i++)
    {
        sum=v[i]-v[i-k];
        while(!c.empty()&&v[i]-v[c.front()-1]<sum) {c.pop();}
        c.push(i-k+1);
        sum=v[i]-v[c.front()-1];
        if(sum>best)
        {
            best=sum;
            st=c.front();
            dr=i;
        }
    }
    g<<st<<" "<<dr<<" "<<best;
    return 0;
}