Cod sursa(job #3281091)

Utilizator Floroiu_MariusFloroiu Marius Cristian Floroiu_Marius Data 28 februarie 2025 12:28:41
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
int n,k;
int x;
int sp[50003];
deque<int> q;
struct raspuns
{
    int st,dr;
    int Min;
}rez;
int main()
{
    fin>>n>>k;
    for (int i=1;i<=n;i++)
    {
        fin>>x;
        sp[i]=sp[i-1]+x;
    }
    rez.Min=sp[k];
    rez.st=1,rez.dr=k;
    q.push_front(0);
    for (int i=k+1;i<=n;i++)
    {
        while (!q.empty() && sp[i-k]<=sp[q.back()]) q.pop_back();
        q.push_back(i-k);
        if (sp[i]-sp[q.front()]>rez.Min)
        {
            rez.Min=sp[i]-sp[q.front()];
            rez.st=q.front()+1;
            rez.dr=i;
        }
    }
    fout<<rez.st<<" "<<rez.dr<<" "<<rez.Min;
    return 0;
}