Cod sursa(job #2306531)

Utilizator UnseenMarksmanDavid Catalin UnseenMarksman Data 22 decembrie 2018 15:12:14
Problema Secventa 2 Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <bits/stdc++.h>
#define maxn 50000
using namespace std;

ifstream fin("secv2.in");
ofstream fout("secv2.out");

long long n, k, v[maxn+2], maxim=INT_MIN, posi, posj;
deque<long long>dq;

int main()
{
    fin>>n>>k;
    for(int i=1; i<=k; i++)
    {
        fin>>v[i];
        v[i]+=v[i-1];
    }
    if(v[k]>maxim)
    {
        posi=k;
        posj=1;
        maxim=v[k];
    }
    for(int i=k+1; i<=n; i++)
    {
        fin>>v[i];
        v[i]+=v[i-1];

        while(!dq.empty()&&v[i-k]<v[dq.back()]) dq.pop_back();

        dq.push_back(i-k);
        if(v[i]-v[dq.front()]>maxim)
        {
            maxim=v[i]-v[dq.front()];
            posi=i;
            posj=dq.front()+1;
        }
    }
    fout<<posj<<' '<<posi<<' '<<maxim<<'\n';
    return 0;
}