#include<stdio.h>
#include<string.h>
int main()
{long long n,q;
char op[10];
int i,j;
long w,k,max;
char a[]=“RowAdd”;
char b[]=“ColAdd”;
scanf("%lld %lld",&n,&q);
long long grid[n][n];
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
grid[i][j]=0;
}
while(q–)
{
scanf("%s %d %d",op,&w,&k);
if(strcmp(op,“RowAdd”)==0)
{for(j=1;j<=n;j++)
grid[w][j]=grid[w][j]+k;
}
else if(strcmp(op,b)==0)
{for(i=1;i<=n;i++)
grid[i][w]=grid[i][w]+k;
}
}
max=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{if(grid[i][j]>max)
max=grid[i][j];
}
}
printf("%d\n",max);
}
Well,
You could use the fact that updates are applied to whole row or column…
On the basis of this fact, we can process the two smaller problems easily
- Find row which have the maximum value, considering only row updates
- Find column which have the maximum value, considering only column updates…
The final answer of this problems is just the sum of answers of above two sub-problems…
Now,
maintain an array R of size N, apply only row updates to the element at row_no index of R.
for example, RowAdd 1 5
just add 5 to R1
answer to this sub-problem is the maximum of this array R…
Similarly the other sub-problem can be solved…
You may have a look at my code here
Please Upvote if you find this helpful… Feel free to ask anything…