Codeforces problem div 2 (skyscrapers)

1

hey can anyone help in this problem please?
problem : https://codeforces.com/contest/1313/problem/C2

Thanks in advance!

2

The condition very clearly implies that there are no valleys. That means there will be some peak, and the heights would be increasing from both sides. The highest sum is obtained, when we let h_i be the minimum of all m_i to the right till the peak. find the maximum sum from the right and left for each node, and calculate the index at which it is maximised. Then using the same method, reconstruct the stack till the index, and then assign values.

My Implementation 
struct node{
    ll value, sum;
    int idx;
};
void solve(){
    int n;
    cin>>n;
    vector<int> seq(n);
    cin>>seq;
    stack<node> blocks;
    node init;
    init.idx=-1;
    init.sum=0;
    init.value=-1;
    blocks.push(init);
    vector<ll> dpforward(n);
    for(int i=0;i<n;i++){
        node topush;
        topush.idx=i;
        topush.value=seq[i];
        while(blocks.top().value>=topush.value){
            blocks.pop();
        }
        topush.sum=(i-blocks.top().idx)*topush.value + blocks.top().sum;
        blocks.push(topush);
        dpforward[i]=blocks.top().sum;
    }
    while(!blocks.empty()){
        blocks.pop();
    }
    init.idx=n;
    blocks.push(init);
    vector<ll> dpbackward(n);
    for(int i=n-1;i>=0;--i){
        node topush;
        topush.idx=i;
        topush.value=seq[i];
        while(blocks.top().value>=topush.value){
            blocks.pop();
        }
        topush.sum=(blocks.top().idx - i)*topush.value + blocks.top().sum;
        blocks.push(topush);
        dpbackward[i]=blocks.top().sum;
    }
    ll ans=0;
    int anspeak=-1;
    for(int i=0;i<n;i++){
        if(dpforward[i] + dpbackward[i] - seq[i] > ans){
            ans=dpforward[i] + dpbackward[i] - seq[i];
            anspeak=i;
        }
    }
    while(!blocks.empty()){
        blocks.pop();
    }
    init.idx=-1;
    blocks.push(init);
    for(int i=0;i<=anspeak;i++){
        node topush;
        topush.idx=i;
        topush.value=seq[i];
        while(blocks.top().value>=topush.value){
            blocks.pop();
        }
        topush.sum=(i-blocks.top().idx)*topush.value + blocks.top().sum;
        blocks.push(topush);
    }
    vector<int> height(n);
    while(!blocks.empty()){
        int start=blocks.top().idx;
        int val=blocks.top().value;
        blocks.pop();
        if(blocks.empty()){
            break;
        }
        for(int i=start;i>blocks.top().idx;--i){
            height[i]=val;
        }
    }
    init.idx=n;
    blocks.push(init);
    for(int i=n-1;i>=anspeak;--i){
        node topush;
        topush.idx=i;
        topush.value=seq[i];
        while(blocks.top().value>=topush.value){
            blocks.pop();
        }
        topush.sum=(blocks.top().idx - i)*topush.value + blocks.top().sum;
        blocks.push(topush);
    }
    while(!blocks.empty()){
        int start=blocks.top().idx;
        int val=blocks.top().value;
        blocks.pop();
        if(blocks.empty()){
            break;
        }
        for(int i=start;i<blocks.top().idx;i++){
            height[i]=val;
        }
    }
    cout+height;
}
3

hey your approach is not clear to me. Can you please elaborate?
Thanks for responding.

4

Say building i is the peak. That means a_{i-1} is less than a_i.
a_i = m_i, because it’s the peak, and it has no reason to be smaller. a_{i-1}\leq a_i, since i is the peak. So if m_{i-1} is larger than a_i, a_{i-1} will be equal to a_{i}. if m_{i-1}<a_i, then a_{i-1} will be equal to m_i. Continuing this reasoning, we can deduce that a_j is the minimum of m_j\dots m_i . Similarly for j>i, a_j is the minimum of m_i \dots m_j .Now you just have to calculate \sum a for all possible peaks i, and find the maximum.

5

Thanks for your explanation!