Cod sursa(job #3363240)

Utilizator CorvinJudge0Corvin Judge CorvinJudge0 Data 14 august 2026 13:36:27
Problema Secventa 2 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

deque<int>dq;
struct maxime {
    int m, ind;
};
int n, k, sp[500008],a,sum_max=0, st=0, dr=0;

maxime max1[50008];

int main()
{
    fin>>n>>k;
    for (int i=1;i<=n;i++)
    {
        fin>>a;
        sp[i]=sp[i-1]+a;

    }
    max1[n+1].m=-1e9;
    for (int i=n;i>=1;i--)
    {
        if (max1[i+1].m<sp[i])
        {
            max1[i].m=sp[i];
            max1[i].ind=i;
        }
        else
        {
            max1[i].m=max1[i+1].m;
            max1[i].ind=max1[i+1].ind;
        }

    }

    for (int i=0;i<=n-k;i++)
    {
        while (!dq.empty() && sp[dq.back()]>sp[i])
        {
            dq.pop_back();
        }
        dq.push_back(i);
         if (sum_max<max1[dq.front()+k].m-sp[dq.front()])
        {
            sum_max=max1[dq.front()+k].m-sp[dq.front()];
            st=dq.front()+1;
            dr=max1[dq.front()+k].ind;
        }
    }
        fout<<st<<' '<<dr<<' '<<sum_max;
}