Cod sursa(job #2124347)

Utilizator nicholascantarNicholas David Cantar Gogitidze nicholascantar Data 7 februarie 2018 09:40:50
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <fstream>
#include <queue>
using namespace std;
queue<int>que;
int n, k,best,e,st,v[50002];
int main()
{
    ifstream fin ("secv2.in");
    ofstream fout ("secv2.out");
    fin >> n >> k;
    for(int i = 1; i <= n; i ++){

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

    que.push(1); best = v[k]; st = 1, e = 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;
    return 0;
}