Cod sursa(job #1249482)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 27 octombrie 2014 00:00:55
Problema Secventa 2 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>

using namespace std;

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

int n, k, v[50500], p, u, st, dr, i, D[50500], s,secv;
int main()
{
    int max = -2000000000;
    fin >> n >> k;
    for(i = 1; i<= n; i ++){
        fin >> v[i];
        while(p <= u && v[i] < v[D[u]]){
            u --;
        }
        D[++u] = i;
        secv ++;
        s += v[D[u]];
        while(i - D[p] + 1 >= k && s - v[D[p]] >= s){
            s -= v[D[p]];
            p ++;
            secv -= D[p] - D[p - 1];
    }
        if(i >= k)
            if(s > max){
                max = s;
                st = D[u] - secv + 1;
                dr = D[u];
            }
    }
    fout << st << " "<< dr << " " << max;
    return 0;
}