Cod sursa(job #2124351)

Utilizator stefantagaTaga Stefan stefantaga Data 7 februarie 2018 09:43:19
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>
#include <queue>
using namespace std;
ifstream f("secv2.in");
ofstream g("secv2.out");
int v[50001],x,n,k,i,e,st,best,sum;
queue <int> q;
int main()
{
    f>>n>>k;
    for (i=1;i<=n;i++)
    {
        f>>x;
        v[i]=v[i-1]+x;
    }
    q.push(1);
    e=k;
    st=1;
    best=v[k];
    for (i=k+1;i<=n;i++)
    {
        sum=v[i]-v[i-k];
        while (!q.empty()&&v[i]-v[q.front()-1]<sum)
        {
            q.pop();
        }
        q.push(i-k+1);
        sum=v[i]-v[q.front()-1];
        if (sum>best)
        {
            best=sum;
            st=q.front();
            e=i;
        }
    }
    g<<st<<" "<<e<<" "<<best;
    return 0;
}