Basketball Exercise Codeforce 1195C Editorial Explained

This is another editorial post of the codeforce problem Basketball Exercise.

Get Free Guide To Competitive Programming along with Programming Techniques
Loading

Detailed BasketBall Exercise Editorial

The problem is basically a DP problem where we have the choice to choose such that  no consecutive chosen students belong to the same row and that the total height of all chosen students is maximum possible.

Basically we will chose players such that if we chose a player from first row then next time we have to choose it from the next row.

So, this is the option we have,
If we choose a player from row A, then total height would be,

A[i] = max(A[i-1], A[i] + B[i-1])

In the above equation we either choose or not choose the current player from row A.

If we choose the current player, total height would be A[i]+B[i-1] which indicates that we height will be player from row A + height of previous player from row A.

If we don’t choose the current player the total current height would height of A[i-1] players.

The above equation takes care of our limitation. We will find heights for both the case and last we will chose the maximum of it.

Hope editorial is clear, if you have any doubts, ask in comment section.

Detailed Code in C++

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
 
int32_t main()
{
    ll t = 1;
    
    while(t--)
    {
        ll n;
        cin >> n;
        
        vector<ll> A(n+1), B(n+1);
        
        for(int i = 1; i <= n; i++) cin >> A[i];
        for(int i = 1; i <= n; i++) cin >> B[i];
        
        A[0] = 0, B[0] = 0;
        
        for(int i = 1; i <= n; i++)
        {
            A[i] = max(A[i-1], A[i] + B[i-1]);
            B[i] = max(B[i-1], B[i] + A[i-1]);
        }
        
        cout<<max(A[n], B[n])<<"\n";
    }
    return 0;
}

Hope You Like BasketBall Exercise editorial of Codeforce, Have a Look on our these 2 editorial Little Girl and Maximum Sum and Mashmokh And ACM Editorial

Leave a Comment

Your email address will not be published. Required fields are marked *