Cod sursa(job #1986569)

Utilizator giotoPopescu Ioan gioto Data 28 mai 2017 16:42:50
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <cstdio>
using namespace std;

int n, k, x, Sum[50005], dq[50005];
int main()
{
    freopen("secv2.in", "r", stdin);
    freopen("secv2.out", "w", stdout);
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n ; ++i){
        scanf("%d", &x);
        Sum[i] = Sum[i - 1] + x;
    }
    int Sol = -2000000000, st = 0, dr = 0, Front = 1, Back = 0;
    for(int i = k; i <= n ; ++i){
        int j = i - k;
        while(Front <= Back && Sum[j] <= Sum[dq[Back]]) --Back;
        dq[++Back] = j;
        if(Sum[i] - Sum[dq[Front]] > Sol){
            Sol = Sum[i] - Sum[dq[Front]];
            st = dq[Front] + 1; dr = i;
        }
    }
    printf("%d %d %d", st, dr, Sol);
    return 0;
}