Cod sursa(job #3268813)

Utilizator jumaracosminJumara Cosmin-Mihai jumaracosmin Data 17 ianuarie 2025 16:50:13
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;

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

const int SIZE = 50005;

int n, k;
int a[SIZE];
int s[SIZE];
deque<int> dq;
int st, dr;

int main()
{
    // citim sirul

    fin >> n >> k;
    for(int i = 1; i <= n; ++i)
        fin >> a[i], s[i] = s[i - 1] + a[i];

    dq.push_back(0);

    int sum_max = s[k];
    st = 1;
    dr = k;

    for(int i = k + 1; i <= n; ++i)
    {
        while(!dq.empty() && s[dq.back()] >= s[i - k])
            dq.pop_back();
        dq.push_back(i - k);
        if(dq.front() == i - n)
            dq.pop_front();

        int sum_noua = s[i] - s[dq.front()];
        if(sum_noua > sum_max)
            sum_max = sum_noua, st = dq.front() + 1, dr = i;
    }

    fout << st << " " << dr << " " << sum_max;

    return 0;
}