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;
}

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

Link: B. Facetook Priority Wall

This is my solution.

bool comp(const pair<int, string>&a, const pair<int, string>&b){
    if(a.first != b.first) return a.first > b.first;
    return a.second < b.second;
}

int main(){
    int n = 0;
    string s, ch;
    getline(cin, s, 'n');
    getline(cin, ch, 'n');
    for(int i=0; i<ch.size() ;i++)
        n=n*10+ch[i]-'0';
    map<string, int> mapa;
    for(int i=0; i<n ;i++){
        getline(cin, ch, 'n');
        stringstream ss(ch);
        vector<string> v;
        while(ss>>ch) v.push_back(ch);
        if(mapa.find(v[0]) == mapa.end())
            mapa[v[0]] = 0;
        if(v.size() == 4){
            string auxs = v[2].substr(0, v[2].size()-2);
            if(mapa.find(auxs) == mapa.end())
                mapa[auxs] = 0;
            if(auxs == s || v[0] == s)
                mapa[v[0]] += 5, mapa[auxs] += 5;
        }
        else{
            string auxs = v[3].substr(0, v[3].size()-2);
            if(mapa.find(auxs) == mapa.end())
                mapa[auxs] = 0;
            if(auxs == s || v[0] == s){
                if(v[4] == "wall")
                    mapa[v[0]] += 15, mapa[auxs] += 15;
                else
                    mapa[v[0]] += 10, mapa[auxs] += 10;
            }
        }
    }
    vector<pair<int, string> > conj;
    for(map<string, int>::iterator it = mapa.begin(); it!=mapa.end() ;it++)
        if(it->first != s)
            conj.PB(MP(it->second, it->first));
    sort(conj.begin(), conj.end(), comp);
    for(int i=0; i<conj.size() ;i++)
        cout<<conj[i].second<<endl;
}