Cod sursa(job #2605542)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 25 aprilie 2020 13:38:34
Problema Secventa 2 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <cstdio>
#include <climits>
using namespace std;
const int NMAX = 50000;
const long long NINF = LONG_LONG_MIN;
int d[NMAX + 5][20] , log[NMAX + 5] , n;
long long sp[NMAX + 5];
void rmq()
{
    int i , j;
    for(i = 1 ; i <= n ; i ++)
        d[i][0] = i;
    for(j = 1 ; (1 << j) <= n ; j ++)
        for(i = 1 ; i + (1 << j) - 1 <= n ; i ++)
            if(sp[d[i][j - 1]] >= sp[d[i + (1 << (j - 1))][j - 1]])
                d[i][j] = d[i][j - 1];
            else
                d[i][j] = d[i + (1 << (j - 1))][j - 1];
}
int query(int x , int y)
{
    int j = log[y - x + 1] - 1;
    if(sp[d[x][j]] >= sp[d[y - (1 << j) + 1][j]])
        return d[x][j];
    return d[y - (1 << j) + 1][j];
}
int main()
{
    freopen("secv2.in" , "r" , stdin);
    freopen("secv2.out" , "w" , stdout);
    int i , k , x , st , dr , poz;
    long long vmax;
    scanf("%d%d" , &n , &k);
    for(i = 1 ; i <= n ; i ++)
    {
        scanf("%d" , &x);
        sp[i] = sp[i - 1] + 1LL * x;
        log[i] = log[i - 1];
        if((i & (i - 1)) == 0)
            log[i] ++;
    }
    rmq();
    vmax = NINF;
    for(i = 1 ; i <= n - k ; i ++)
    {
        poz = query(i + k , n);
        if(sp[poz] - sp[i - 1] > vmax)
        {
            vmax = sp[poz] - sp[i - 1];
            st = i;
            dr = poz;
        }
    }
    printf("%d %d %lld\n" , st , dr , vmax);
    return 0;
}