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 C

Link: C. Modified GCD

This is my solution.

int main(){
    int a, b, n, x, y;
    scanf("%d %d %d", &a, &b, &n);
    int d = __gcd(a, b);
    set<int> v;
    v.insert(d);
    for(int i=1; i <= sqrt(d) ;i++){
        if(d%i == 0){
            v.insert(i);
            v.insert(d/i);
        }
    }
    vector<int> val(v.begin(), v.end());
    for(int i=0; i<n ;i++){
        scanf("%d %d", &x, &y);
        a = 0, b = val.size()-1;
        while(a != b){
            int mid = ((a+b)/2)+1;
            if(val[mid] > y) b = mid-1;
            else a = mid;
        }
        int r=-1;
        if(a+1 < val.size()){
            if(val[a+1] <= y && val[a+1] >= x)
                r = val[a+1];
        }
        if(val[a] <= y && val[a] >= x)
            r = max(val[a], r);
        if(a-1 >= 0){
            if(val[a-1] <= y && val[a-1] >= x)
                r = max(r, val[a-1]);
        }
        printf("%dn", r);
    }
}

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

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

Link: A. Life Without Zeros

In this problem, had to create a function to remove zeros, like this:

int removeZeros(int n){
    int r = 0, ten = 1;
    while(n){
        if(n%10){
            r += (n%10)*ten;
            ten *= 10;
        }
        n /= 10;
    }
    return r;
}

Below is my solution.

int removeZeros(int n){
    int r = 0, ten = 1;
    while(n){
        if(n%10){
            r = r + (n%10)*ten;
            ten *= 10;
        }
        n /= 10;
    }
    return r;
}

int main(){
    int n, m;
    cin>>n>>m;
    if(removec(n+m) == removec(n)+removec(m)) printf("YESn");
    else printf("NOn");
}