➤ Problem Link : ANARC05B
👉 Hint : Binary search with cumulative array
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
int n,m;
int ar1[10002];
int ar2[10002];
ll cum1[10002];
ll cum2[10002];
while(1)
{
cin>>n;
if(n==0)
break;
memset(ar1,0,sizeof(ar1));
memset(ar2,0,sizeof(ar2));
for(int i=1;i<=n;i++)
cin>>ar1[i];
cin>>m;
for(int i=1;i<=m;i++)
cin>>ar2[i];
int i=0;
memset(cum1,0,sizeof(cum1));
memset(cum2,0,sizeof(cum2));
cum1[1]=ar1[1];
cum2[1]=ar2[1];
for(i=2;i<=n;i++)
{
cum1[i]=cum1[i-1]+ar1[i];
}
for(i=2;i<=m;i++)
{
cum2[i]=cum2[i-1]+ar2[i];
}
cum1[0]=0;
cum2[0]=0;
int ix=0,iy=0;
ll ans=0,sum=0,su=0;
for(i=1;i<=n;i++)
{
if(binary_search(ar2+iy+1,ar2+m+1,ar1[i]))
{
int y=lower_bound(ar2+iy+1,ar2+m+1,ar1[i])-ar2;
if(cum1[i]-cum1[ix] > cum2[y]-cum2[iy])
ans+=cum1[i]-cum1[ix];
else
ans+=cum2[y]-cum2[iy];
iy=y;
ix=i;
}
}
ix++,iy++;
while(ix<=n)
sum+=ar1[ix++];
while(iy<=m)
su+=ar2[iy++];
ans+=max(sum,su);
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.