Cod sursa(job #2836704)

Utilizator MariusDinsorea32DinsoreanMarius MariusDinsorea32 Data 20 ianuarie 2022 19:32:46
Problema Secventa 2 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;

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

const int N = 5e4 + 7;
int n, i, k, l, r;
long long smax;
long long s[N];

deque <int> deq;

int main()
{
    fin >> n >> k;
    for(i = 1; i <= n; i++)
        fin >> s[i], s[i] += s[i - 1];
    for(i = k; i <= n; i++){
        while(!deq.empty() && s[i] - s[i - k] >= s[i] - s[deq.back()])
            deq.pop_back();
        deq.push_back(i - k);

        if(smax <= s[i] - s[deq.front()]){
            smax = s[i] - s[deq.front()];
            l = deq.front() + 1;
            r = i;
        }
    }
    fout << l << " " << r << " " << smax;
    return 0;
}