Cod sursa(job #3148659)

Utilizator maryyMaria Ciutea maryy Data 3 septembrie 2023 09:56:27
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream in("secv2.in");
ofstream out("secv2.out");
int v[50001], sp[50001];
int main()
{
    int n, k;
    in>>n>>k;
    for(int i=1; i<=n; i++)
    {
        in>>v[i];
        sp[i]=sp[i-1]+v[i];
    }
    deque <int> q;
    int maxi=-1250000000;
    int st=0, dr=0;
    for(int i=k; 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()]>maxi)
        {
            maxi=sp[i]-sp[q.front()];
            st=q.front()+1;
            dr=i;
        }
    }
    out<<st<<" "<<dr<<" "<<maxi;
}