Table Sum, INOI 2012

Problem Description

Question : Table Sum, INOI 2012

Submit Code : Codechef

Prerequisites

Arrays

Solution

Let see how the solution will be affected by rotating the second table.

$$\begin{array}{|c|c|c|c|} \hline 7 & 1 & 6 & 2 \\ \hline 1 & 2 & 3 & 4 \\ \hline 8 & 3 & 9 & 6 \\ \hline - & - & - & - \\ \hline \end{array} = 9$$

$$\Rightarrow \begin{array}{|c|c|c|c|} \hline 7 & 1 & 6 & 2 \\ \hline 2 & 3 & 4 & 1 \\ \hline 9 & 4 & 10 & 3 \\ \hline +1 & +1 & +1 & 2 + 1 \\ \hline \end{array} = 10$$

$$\Rightarrow \begin{array}{|c|c|c|c|} \hline 7 & 1 & 6 & 2 \\ \hline 3 & 4 & 1 & 2 \\ \hline 10 & 5 & 7 & 4 \\ \hline +1 & +1 & 6 + 1 & (2 + 1) + 1 \\ \hline \end{array} = 10$$

$$\Rightarrow \begin{array}{|c|c|c|c|} \hline 7 & 1 & 6 & 2 \\ \hline 4 & 1 & 2 & 3 \\ \hline 11 & 2 & 8 & 5 \\ \hline +1 & 1 + 1 & (6 + 1) + 1 & ((2 + 1) + 1) + 1 \\ \hline \end{array} = 11$$

You can see that each answer can be calculated through previous calculated answers.

Code

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> arr(n);
    
    for(int& i : arr)
        cin >> i;

    vector<int> bmax(n);
    bmax[0] = arr[0]+1;
    for(int i=1;i<n;i++)
        bmax[i] = max(bmax[i-1], arr[i]+i+1);

    int emax = 0;
    for(int i=0;i<n;i++){
        cout << max(bmax[n-i-1]+i, emax) << " ";
        emax = 1 + max(arr[n-i-1], emax);
    }
    return 0;
}