➤ Problem Link : 463C. Gargari and Bishops
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
ll arr[n+1][n+1];
ll cumLR[n+1][n+1];
ll cumRL[n+1][n+1];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cin>>arr[i][j];
}
int i=n-1,k,j=0;
while(i>=0)
{
for(k=i,j=0;k<n && j<n;k++,j++)
{
if(j==0)
cumLR[k][j]=arr[k][j];
else
cumLR[k][j]=arr[k][j]+cumLR[k-1][j-1];
}
i--;
}
i=1;
while(i<n)
{
for(k=0,j=i;k<n && j<n;k++,j++)
{
if(k==0)
cumLR[k][j]=arr[k][j];
else
cumLR[k][j]=arr[k][j]+cumLR[k-1][j-1];
}
i++;
}
i=0;
while(i<n)
{
for(k=0,j=i;k<n && j>=0;k++,j--)
{
if(k==0)
cumRL[k][j]=arr[k][j];
else
cumRL[k][j]=arr[k][j]+cumRL[k-1][j+1];
}
i++;
}
i=1;
while(i<n)
{
for(k=i,j=n-1;k<n && j>=0;k++,j--)
{
if(j==n-1)
cumRL[k][j]=arr[k][j];
else
cumRL[k][j]=arr[k][j]+cumRL[k-1][j+1];
}
i++;
}
int oddi=0,oddj=1,eveni=0,evenj=0;
ll oddval=-1,evenval=-1,val;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i<j)
val=cumLR[i+n-1-j][n-1];
else
val=cumLR[n-1][j+n-1-i];
//cout<<val<<" ";
if(i+j<n)
val+=cumRL[i+j][0]-arr[i][j];
else
val+=cumRL[n-1][i+j-n+1]-arr[i][j];
// cout<<val<<" ";
if((i+j)%2==1)
{
if(val>oddval)
{
oddval=val;
oddi=i+1;
oddj=j+1;
}
}
else
{
if(val>evenval)
{
evenval=val;
eveni=i+1;
evenj=j+1;
}
}
}
}
cout<<oddval+evenval<<"\n";
cout<<oddi<<" "<<oddj<<" ";
cout<<eveni<<" "<<evenj<<"\n";
}
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.