304 North Cardinal St.
Dorchester Center, MA 02124

# Matrix CodeChef Solution

## Matrix CodeChef Solution in C++17

``````

#include <stdio.h>
#include <algorithm>
using namespace std;

int i,j,n,m,a[2005][2005],c[2005],last;
long long ret;

int main (int argc, char * const argv[]) {
scanf("%d%d\n",&n,&m); // size of the matrix
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)a[i][j]=getchar()-'0'; // reading the matrix. scanf might be too slow here, so getchar is recommended
}
for(i=n;i;i--){ // calculate answers from the bottom to the top
for(j=1;j<=m;j++)if(a[i][j])++c[j];else c[j]=0; // c[j] naturally equals to the amount of consecutive cells with ones right under the cell (i, j)
for(j=1,last=0;j<=m;j++)ret+=last=min(last+1,c[j]); // calculate the answers according to the formula
}
return 0;
}``````

## Matrix CodeChef Solution in C++14

``````#include <bits/stdc++.h>
#define ll long long
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define fi first
#define se second
#define oo 1e18
#define bit(x,i) (((x)>>(i))&1)
using namespace std;
const int MOD = 1e9 + 7;
const int N = 2e3 + 5;
int t,n,m,dp[N][N];
char a[N][N];
int main()
{
#ifndef ONLINE_JUDGE
freopen("new.inp","r",stdin);
freopen("new.out","w",stdout);
#endif // ONLINE_JUDGE
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
fo(i,1,n)
{
fo(j,1,m)
cin>>a[i][j];
}
fo(j,1,m)
{
fo(i,1,n/2)
swap(a[i][j], a[n-i+1][j]);
}
ll ans = 0;
fo(i,1,n)
{
fo(j,1,m)
{
if(a[i][j] == '1')
{
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1;
ans += dp[i][j];
}
}
}
cout<<ans;
}``````

## Matrix CodeChef Solution in PYTH 3

``````# cook your dish here
n,m=[int(c) for c in input().split()]
matrix = []
for i in range(n):
arr =[int(c) for c in input()]
matrix.append(arr)

c = [0 for i in range(m)]
ans = 0
for i in range(n-1,-1,-1):
last = 0
for j in range(m):
c[j] = 0 if not matrix[i][j] else c[j]+1

for j in range(m):
last = min(last + 1,c[j])
ans+=last

print(ans)
``````

## Matrix CodeChef Solution in C

``````#include <stdio.h>

#define min(a,b) a>b?b:a

int m,n,i,j;
short A[2000][2000];
long long int sum=0;
int main()
{
char c='\0';
scanf("%d%d",&n,&m);

for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
scanf(" %c",&c);
A[i][j]=c-'0';
if(i&&j)
{
if(A[i][j]==1)
{
A[i][j]+=min(A[i-1][j],A[i-1][j-1]);
}
}
sum+=A[i][j];

}
}
printf("%lld\n",sum);
return 0;
}``````

## Matrix CodeChef Solution in JAVA

``````/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
sc.nextLine();
String arr[] = new String[n];
for(int i = 0 ; i < n ; i++)
{
arr[i] = sc.nextLine();
}

int dp[][] = new int[n][m];
for(int i = n-1 ; i >= 0 ; i--)
{
for(int j = m-1; j >= 0 ; j--)
{
if(arr[i].charAt(j) == '0')
dp[i][j] = 0;

else
{
if(i+1 >= n || j+1 >= m)
dp[i][j] = 1;

else
{
dp[i][j] = 1+dp[i+1][j+1];
}
}
}
}

for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < m ; j++)
{
dp[i][j] = Math.min(m-1,j+dp[i][j]-1);
}
}

long ans = 0;
TreeMap<Integer,Integer> map = new TreeMap<Integer,Integer>();
for(int i = 0 ; i < n ; i++)
{
int j = 0 , k = 0;
map.clear();
map.put(dp[i][0],1);
while(j < m && k < m)
{
if(map.firstKey() < k)
{
while(j <= k && map.firstKey() < k)
{
if(map.get(dp[i][j]) == 1)
map.remove(dp[i][j]);

else
map.put(dp[i][j],map.get(dp[i][j])-1);

j++;

}

ans += k-j+1;
k++;

if(k < m)
{
if(map.containsKey(dp[i][k]))
map.replace(dp[i][k],map.get(dp[i][k])+1);

else
map.put(dp[i][k],1);
}
}

else
{
ans += k-j+1;
if(k+1 < m)
{
if(map.containsKey(dp[i][k+1]))
map.replace(dp[i][k+1],map.get(dp[i][k+1])+1);

else
map.put(dp[i][k+1],1);

}
k++;
}
}
}

System.out.println(ans);
}
}``````

## Matrix CodeChef Solution in PYPY 3

``````import sys
n,m=map(int,input().split())
a=[[0]*m for _ in range(n)]
for i in range(n):
for j in range(m):
if s[j]=='1':
a[i][j]=1
ans=0
left=[[0]*m for _ in range(n)]
bottom=[[0]*m for _ in range(n)]
dp=[[0]*m for _ in range(n)]
#let's fill left
for i in range(n):
for j in range(m):
if a[i][j]==0:
continue
left[i][j]=1+left[i][j-1]
#let's fill bottom
for i in range(n-1,-1,-1):
for j in range(m):
if a[i][j]==0:
continue
bottom[i][j]=1+bottom[(i+1)%n][j]
for i in range(n):
if a[i][0]==1:
dp[i][0]=1
for j in range(m):
if a[-1][j]==1:
dp[-1][j]=1
for i in range(n-2,-1,-1):
for j in range(1,m):
if a[i][j]==1:
dp[i][j]=min(dp[i+1][j-1]+1,left[i][j-1],bottom[i+1][j])+1
print(sum(map(sum,dp)))``````

## Matrix CodeChef Solution in PYTH

``````n,m=map(int,raw_input().split())

l=[]

for i in range(n):

l.append(map(int,raw_input()))

mat = [[0 for i in range(m)] for j in range(n)]

for i in range(n):
for j in range(m):
if i==0 or j == 0:
mat[i][j]=l[i][j]
else:
if l[i][j]:
mat[i][j] = min(mat[i-1][j],mat[i-1][j-1]) + 1
ans=0
for i in range(n):
for j in range(m):
ans+=mat[i][j]
print ans
``````
##### Matrix CodeChef Solution Review:

In our experience, we suggest you solve this Matrix CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Matrix CodeChef Solution.

Find on CodeChef

##### Conclusion:

I hope this Matrix CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!