➤ Problem Link : GERGOVIA
👉 Hint : Greedy approach
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
int main()
{
vector<pair<int,int> >v_pos;
vector<pair<int,int> >v_neg;
while(1)
{
v_pos.clear();
v_neg.clear();
int n,x;
long long int ans=0;
cin>>n;
if(!n)
break;
for(int i=0;i<n;i++)
{
cin>>x;
if(x>0)
v_pos.push_back(make_pair(x,i));
else if(x<0)
v_neg.push_back(make_pair(-x,i));
}
int p=0,q=0;
while(p<v_pos.size() && q<v_neg.size())
{
if(v_pos[p].first>v_neg[q].first)
{
ans+=abs(v_pos[p].second-v_neg[q].second)*v_neg[q].first;
v_pos[p].first-=v_neg[q].first;
q++;
}
else if(v_pos[p].first<v_neg[q].first)
{
ans+=abs(v_pos[p].second-v_neg[q].second)*v_pos[p].first;
v_neg[q].first-=v_pos[p].first;
p++;
}
else
{
ans+=abs(v_pos[p].second-v_neg[q].second)*v_pos[p].first;
p++;q++;
}
}
cout<<ans<<endl;
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.