Cod sursa(job #2707853)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 17 februarie 2021 20:44:01
Problema Secventa Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
//Ilie Dumitru
#include<cstdio>

int N, K, pos, val;
int arb[1000010];

void updt(int nod, int a, int b)
{
    if(a!=b)
    {
        int m=(a+b)>>1, x, y;
        if(pos<=m)
            updt(nod<<1, a, m);
        else
            updt((nod<<1)+1, m+1, b);
        x=arb[nod<<1];
        y=arb[(nod<<1)+1];
        arb[nod]=x+(y-x)*(y<x);
    }
    else
        arb[nod]=val;
}

inline int best(){return arb[1];}

int main()
{
    int i, minim=-30001, posmin=0, x;
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
    scanf("%i", &N);
    scanf("%i", &K);
    for(i=0;i<K;++i)
    {
        scanf("%i", &val);
        pos=i+1;
        updt(1, 1, K);
    }
    for(;i<N;++i)
    {
        x=best();
        if(x>minim)
        {
            minim=x;
            posmin=i;
        }
        pos=i%K+1;
        scanf("%i", &val);
        updt(1, 1, K);
    }
    fclose(stdin);
    x=best();
    if(x>minim)
    {
        minim=x;
        posmin=i;
    }
    printf("%i %i %i", posmin-K+1, posmin, minim);
    fclose(stdin);
    return 0;
}