TESTP03 - Editorial

editorial
1

PROBLEM LINK:

Practice
Div-2 Contest

Author: Vivek Kumar Mishra
Tester: Harshit Pandey
Editorialist: Harshit Sharma

DIFFICULTY:

EASY

PREREQUISITES:

Stacks

PROBLEM:

Find whether Peter can score equal marks

QUICK EXPLANATION:

Use stack algorithm to find the answer.

EXPLANATION:

We can use a stack data structure. We will only pop elements from the stack. We can only decrease its sum as it is guaranteed that there are only positive integers in the stack.
So we just take the stack with the highest sum and pop elements from it until we can find that the sum is equal in all three stacks.

SOLUTIONS:

Setter's Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define line “\n”
#define vi vector
#define mi map<ll,ll>
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define check(x) cout<<“Check#”<<x<<line;
#define p_c(x) __builtin_popcountll(x)
#define show(x) for(auto it:x)cout<<it<<" “;
const ll int MX=1e9+7;
void Case(ll int x,ll int t){cout<<“Case #”<<x-t<<”: ";}

ll int maxSum(stack &stk1, stack &stk2, stack &stk3){
int sum1=0,sum2=0,sum3=0;
stack s1=stk1,s2=stk2,s3=stk3;
while(!s1.empty()){
sum1+=s1.top();
s1.pop();
}
while(!s2.empty()){
sum2+=s2.top();
s2.pop();
}
while(!s3.empty()){
sum3+=s3.top();
s3.pop();
}
if(sum1==sum2 and sum2==sum3)return sum1;
while(true){
if(stk1.empty() or stk2.empty() or stk2.empty())return 0;
if(sum1==sum2 and sum2==sum3)return sum1;
if(sum1==max(sum1,max(sum2,sum3))){
sum1-=stk1.top();
stk1.pop();
}
else
if(sum2==max(sum1,max(sum2,sum3))){
sum2-=stk2.top();
stk2.pop();
}
else
if(sum3==max(sum1,max(sum2,sum3))){
sum3-=stk3.top();
stk3.pop();
}

}
return 0;

}

void solve(){

ll int n1,n2,n3;
cin>>n1>>n2>>n3;
stack<int> st1,st2,st3;
vi arr1(n1),arr2(n2),arr3(n3);
for(int i=0;i<n1;i++){
    cin>>arr1[i];
    st1.push(arr1[i]);
}
for(int i=0;i<n2;i++){
    cin>>arr2[i];
    st2.push(arr2[i]);
}
for(int i=0;i<n3;i++){
    cin>>arr3[i];
    st3.push(arr3[i]);
}
ll int ans=maxSum(st1,st2,st3);
cout<<ans<<line;
// show(arr1)check("1")

}

int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
ll int t=1;
cin>>t;
while(t–){
solve();
}
return 0;
}