Codeforces Beta Round #67 (Div. 2) Problem D

Link: D. Big Maximum Sum

This is my solution.

typedef long long LL;

int n, v[5010];

struct FOUR{
    LL m, l, r, t;
} T[20010], DP[55];

void crear(int a, int b, int it){
    if(a == b){
        T[it].m = T[it].l = T[it].r = T[it].t = v[a];
        return;
    }
    int mid = (a+b)>>1, left = it<<1, right = left+1;
    crear(a, mid, left);
    crear(mid+1, b, right);
    T[it].t = T[left].t + T[right].t;
    T[it].m = max(max(T[left].m, T[right].m), T[left].r+T[right].l);
    T[it].l = max(max(T[left].l, T[left].t+T[right].l), T[left].t);
    T[it].r = max(max(T[right].r, T[left].r+T[right].t), T[right].t);
}

FOUR unionFour(FOUR auxL, int j){
    FOUR auxR = DP[j], r;
    r.t = auxL.t + auxR.t;
    r.m = max(max(auxL.m, auxR.m), auxL.r+auxR.l);
    r.l = max(max(auxL.l, auxL.t+auxR.l), auxL.t);
    r.r = max(max(auxR.r, auxL.r+auxR.t), auxR.t);
    return r;
}

int main(){
    int m, l, a, ind;
    scanf("%d %d", &n, &m);
    for(int i=0; i<n ;i++){
        scanf("%d", &l);
        for(int j=1; j<=l ;j++)
            scanf("%d", &v[j]);
        crear(1, l, 1);
        DP[i] = T[1];
    }
    scanf("%d", &ind);
    FOUR fr = DP[ind-1];
    for(int i=1; i<m ;i++){
        scanf("%d", &ind);
        fr = unionFour(fr, ind-1);
    }
    cout<< max(max(fr.t, fr.m),max(fr.l, fr.r)) <<endl;
}

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s