How to solve F using a stack?

never get bored of this meme

Solution for D

#include<bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int testCases;
    cin >> testCases;
    while(testCases--){
        int n,MAX=0,MIN=1e10,ans=0;
        cin >> n;
        int A[n],B[n];
        for(int i=0;i<n;i++) cin >> A[i];
        for(int i=0;i<n;i++) cin >> B[i];
        for(int i=0;i<n;i++){
            int cur_abs = abs(A[i]-B[i]);
            ans += cur_abs;
            MAX = max(MAX,A[i]+B[i]-cur_abs);
            MIN = min(MIN,A[i]+B[i]+cur_abs);
        }
        cout << ans + max(0LL,MAX-MIN) << "\n";
    }
}

submission 233513167

Can someone help with the proof of this solution!

i generalized all cases as A1<=B2 and A2>=B1

after swapping the contribution is(b2 - a1) + (a2 - b1) - abs(a1-b1) - abs(a2-b2)

= b2+a2-abs(a2-b2) - (b1+a1+abs(a1-b1))

MAX( b2+a2-abs(a2-b2)) - MIN(b1+a1+abs(a1-b1)) => ans

Is contest starting at 8:30pm IST? The timer is showing half hour left for start of contest

How to solve D?

You will surely be in stable expert and CM

System.out.println() is every slow so I used c++ for this task. If it was not interactive we can use fast output

How to solve C?

Quite strange, with 1024mb its giving MLE and 256mb AC... i have no clue.

But if we reduce thread stack size to 1<<26 it get AC 219687128

This is because of small stack size for recursive calls. We can create a new thread and assign stack size. (1<<26) stack size is sufficent for most recursive tasks.

RTE with default stack size

AC with (1<<26) stack size

My current rating: 1414

Target Rating: 1600+

Number of questions solved: 346

Target: 600 questions

Wish me luck. I am a beginner(started CF 4 months back) but would try my best. Thanks for the motivation

Very nice explanation!! I tried two pointer (sliding window) but no luck