Intermediate.
Put your skills to the test.

Problem summary

Two fence sections have the same number of equal-width boards. Place their uneven ends against each other, optionally reversing one section horizontally. Find the greatest rectangular shield height with no gap.

Constraints

2 ≤ N < 100; each board height is between 100 and 200.

Worked example

Input and output for the worked example discussed below.

3
110 150 140
120 130 135

245

Solution analysis

1. Fix an orientation. In board column i, the two boards cover a total height a[i]+b[i]. A rectangle of height H has no gap exactly when H is at most every one of these sums. Thus this orientation allows min_i(a[i]+b[i]).
2. There are only two distinct alignments: second section in its original order, or reversed. Reversing both changes only the column order and gives no new minimum. Compute the limiting height for both alignments and take the larger.
3. In the example, original pairing sums are 230,280,275, so its limit is 230. Reversing gives 245,280,260, whose limit is 245. The larger feasible shield height is 245.

Why it works

For a fixed orientation each column must be covered, so its pair sum is an upper bound on H; satisfying all these bounds is also sufficient because overlap is permitted. The minimum sum is therefore the exact optimum for that alignment. Enumerating both possible relative orders covers every legal orientation.

Watch out. Maximizing a single pair sum is insufficient: the shortest pair leaves a gap. Boards cannot be rearranged independently; only the entire section may reverse.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>first(n);
    vector<int>second(n);
    for(int&height:first){
        cin>>height;
    }
    for(int&height:second){
        cin>>height;
    }
    int same=1000;
    int reversed=1000;
    for(int i=0;i<n;i++){
        // Every column must be covered in the chosen orientation.
        same=min(same,first[i]+second[i]);
        reversed=min(reversed,first[i]+second[n-1-i]);
    }
    cout<<max(same,reversed)<<'\n';
}