All possible sub-matrices sums.

               

                              Save the nature

https://www.codechef.com/problems/SVNTR (Lunch Time oct 2015)

 In this problem , you have to count number of sub-matrices whose sum is less than or equal to k (given).

Approach for this problem : firstly calculate the all possible column sum , i.e for c number of columns ,there will be c*(c+1)/2 columns created.

 for example : 1 2 3                                 1  3  6   2   5   3
                       4 5 6                 --->>>     4  9  15  5  11  6

  after creating "b" matrix from the given "a"  matrix.  Calculate all possible sums in each columns

In this all possible sum for 1st column is : 1,4,5.

In this all possible sum for 2nd column is : 3,9,12.

now, that count all the sums which is smaller than or equal to "k".

1. #include<bits/stdc++.h>
2.  
3. using namespace std;
4.  
5. long long int b[151][12255],a[151][151];
6.  
7.  
8. int main()
9. {
10. ios_base::sync_with_stdio(0);
11. cin.tie(0);
12. int t;
13. cin>>t;
14. while(t--)
15. {
16. long long int r,c,make,i,j,k,l,p,s,cnt=0;
17. cin>>r>>c>>make;
19. for(i=0;i<r;i++)
20. for(j=0;j<c;j++)
21. cin>>a[i][j];
23. for(p=0;p<r;p++)
24. {
25. k=0;
26. for(i=0;i<c;i++)
27. {
28. s=0;
29. for(j=i;j<c;j++)
30. {
31. s+=a[p][j];
32. b[p][k++]=s;
33. }
34. }
35. }
39. long long int sz=((c*(c+1)));
40. sz=sz/2;
41. for(i=0;i<sz;i++)
42. {
43. for(j=0;j<r;j++)
44. {
45. s=0;
46. for(k=j;k<r;k++)
47. {
48. s+=b[k][i];
49. if(s<=make)
50. cnt++;
51. }
52. }
53. }
55. cout<<cnt<<endl;
56. }
57. return 0;
58. }