Cod sursa(job #2120271)

Utilizator horiainfoTurcuman Horia horiainfo Data 2 februarie 2018 11:08:38
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
/*
    ID : thoria1991
    TASK : barn1
    LANG : C++11
*/

#include <bits/stdc++.h>

using namespace std;

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

int best = -(int)(2e9), v[50002], st, e;
queue<int> que;

int main(){

    int n, k; fin >> n >> k;
    for(int i = 1; i <= n; i ++){

        fin >> v[i];
        v[i] += v[i - 1];
    }

    que.push(1); best = v[k];
    for(int i = k + 1; i <= n; i ++){

        int sum = v[i] - v[i - k];
        while(!que.empty() && v[i] - v[que.front() - 1] < sum)
            que.pop();
        
        que.push(i - k + 1);

        sum = v[i] - v[que.front() - 1];
        if(sum > best)
            best = sum, st = que.front(), e = i;
    }

    fout << st << ' ' << e << ' ' << best;
}