Cod sursa(job #1626076)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 2 martie 2016 22:15:57
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <cstdio>
#include <deque>
using namespace std;

#define DIM 50005
int v[DIM];
int d[DIM];

deque < int  > Q;

int main()
{

    freopen("secv2.in","r",stdin);
    freopen("secv2.out","w",stdout);

    int n, i, j, s, t, k, id,  ma, begi, endi;
    ma = -(1<<29);

    scanf("%d%d",&n,&k);

    scanf("%d",&v[1]);
    d[1] = v[1];
    Q.push_back(1);

    for( i = 2; i <= n; ++i ){
        scanf("%d",&v[i]);
        v[i] += v[i-1];

        d[i] = v[i] - v[Q.front()];
        id = Q.front() + 1;

        while( !Q.empty() && v[Q.back()] > v[i] )
            Q.pop_back();

        Q.push_back(i);

        if( i - id + 1 > k && d[i] > ma ){
            ma = d[i];
            begi = id;
            endi = i;
        }
    }

    printf("%d %d %d",begi,endi,ma);

    return 0;
}