fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int mat[101][101], pre[101][101];
  4. int n, m;
  5.  
  6. int get_sum(int top, int left, int bottom, int right){
  7. 	int sum = 0;
  8. 	for(int i=top; i<=bottom; i++){
  9. 		for(int j=left; j<=right; j++){
  10. 			sum += mat[i][j];
  11. 		}
  12. 	}
  13. 	return sum;
  14. }
  15.  
  16. // pre[i][j] -- sum from (1, 1) to (i, j)
  17. void get_sum(){
  18. 	for(int i = 1; i <= n; i++){
  19. 		for(int j = 1; j <= m; j++){
  20. 			pre[i][j] = get_sum(1, 1, i, j);
  21. 		}
  22. 	}
  23. }
  24.  
  25. int query(int t, int l, int b, int r){
  26. 	return pre[b][r] - pre[t-1][r] - pre[b][l-1] + pre[t-1][l-1];
  27. }
  28.  
  29.  
  30. int main(){
  31. 	cin >> n; m = n;
  32. 	for(int i=1; i<=n; i++){
  33. 		for(int j=1; j<=m; j++){
  34. 			cin >> mat[i][j];
  35. 		}
  36. 	}
  37. 	get_sum();
  38. 	int mx = 1e-9;
  39. 	for(int top = 1; top <= n; top++){
  40. 		for(int left = 1; left <= m; left++){
  41. 			for(int bottom = top; bottom <= n; bottom++){
  42. 				for(int right = left; right <= m; right++){
  43. 					mx = max(mx, query(top, left, bottom, right));			
  44. 				}
  45. 			}
  46. 		}
  47. 	}
  48. 	cout << mx << endl;
  49. }
Success #stdin #stdout 0s 15312KB
comments (?)
stdin
copy 
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2
stdout
copy 
15
https://ideone.com/UExbEQ
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!