# PROBLEM LINK:

**Setter:** a0n0k0i0t

**Tester:** a0n0k0i0t

**Editorialist:** a0n0k0i0t

# PROBLEM

You are travelling on a road with two lanes A and B. You are initially at position 0. You need to reach your home at position N+1. On each of the lane A and B there are N tollbooths which comes in your way to home. The tollbooths are at positions 1,2,3.., N. Cost of crossing i_{th} tollbooth in lane A and lane B is A_i and B_i respectively. You want to reach your home by spending as less money as possible but there are some rules you should follow for your journey:

- you can start your journey at any of the lane A or B and can also end your journey at any of the lane A or B.
- you can switch the lanes at most one time
- you can switch lanes at any of the positions 1,2,3..N

Determine the minimum cost you must pay to reach your home

# DIFFICULTY:

Easy

# PREREQUISITES:

Prefix Sum , Suffix Sum

# EXPLANATION:

### Case I: When you don’t switch lanes

Then the answer is simply the minimum of sum of array A and sum of Array B.

### Case II: When you switch the lane from A to B

In this case if you switch at i_{th} position you are paying ((sum(A_1 to A_i)) + sum(B_i to B_N))

We have to find minimum cost of \forall i \in (1,2,..N).

### Brute-Force (Gives TLE)

One way to do is iterating over all i and compute sum(A_1 to A_i) + sum(B_i to B_N) over all i and find minimum.

### Time complexity: O(N^2)

### Optimized Approach

Instead of computing sum(A_1 to A_i) for all i , we can precompute the prefix sum of the array A in preA , where preA_i = sum(A_1 to A_i) .

`preA[1]=A[1]; (for i==1)`

`preA[i]=preA[i-1]+A[i]; (for 2<=i<=N)`

In similar way to compute sum(B_i to B_N) , we can precomute the suffix sum of the array B in sufB , where sufB_i = sum(B_i to B_N) .

`sufB[N]=B[N]; (for i==1)`

`sufB[i]=sufB[i+1]+B[i]; (for 2<=i<=N)`

Now if you switch lane at i_{th} position cost will be `preA[i]+sufB[i]`

.

Find `min( preA[i]+sufB[i])`

over all i.

### Case III: When you switch the lane from B to A

In this case if you switch at i_{th} position you are paying ((sum(B_1 to B_i)) + sum(A_i to A_N))

This is very similar to Case II ,just you have to find preB and sufA in this case.

`preB[1]=B[1]; (for i==1)`

`preB[i]=preB[i-1]+B[i]; (for 2<=i<=N)`

`sufA[N]=A[N]; (for i==1)`

`sufA[i]=sufA[i+1]+A[i]; (for 2<=i<=N)`

Now if you switch lane at i_{th} position cost will be `preB[i]+sufA[i]`

.

Find `min( preB[i]+sufA[i])`

over all i.

The minimum of all three cases will be the answer required.

## Time Complexity: O(N)

# SOLUTION:

```
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ll T;
cin>>T;
while(T--){
ll n;
cin>>n;
ll a[n];
ll b[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
cin>>b[i];
}
ll pre1[n],pre2[n]; // preA , preB
ll suf1[n],suf2[n]; // sufA , sufB
pre1[0]=a[0];
pre2[0]=b[0];
for(int i=1;i<n;i++){
pre1[i]=pre1[i-1]+a[i];
pre2[i]=pre2[i-1]+b[i];
}
suf1[n-1]=a[n-1];
suf2[n-1]=b[n-1];
for(int i=n-2;i>=0;i--){
suf1[i]=suf1[i+1]+a[i];
suf2[i]=suf2[i+1]+b[i];
}
ll ans=min(pre1[n-1],pre2[n-1]); // Case I
for(int i=0;i<n;i++){
ll path1=pre1[i]+suf2[i];
ll path2=pre2[i]+suf1[i];
ans=min(ans,path1); //Case II
ans=min(ans,path2); //Case III
}
cout<<ans<<"\n";
}
return 0;
}
```