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. // pre[i][j] -- sum from (1, 1) to (i, j)
  7. void get_sum(){
  8. 	for(int i = 1; i <= n; i++){
  9. 		for(int j = 1; j <= m; j++){
  10. 			pre[i][j] = mat[i][j] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]; 
  11. 		}
  12. 	}
  13. }
  14.  
  15. int query(int t, int l, int b, int r){
  16. 	return pre[b][r] - pre[t-1][r] - pre[b][l-1] + pre[t-1][l-1];
  17. }
  18.  
  19.  
  20. int main(){
  21. 	cin >> n; m = n;
  22. 	for(int i=1; i<=n; i++){
  23. 		for(int j=1; j<=m; j++){
  24. 			cin >> mat[i][j];
  25. 		}
  26. 	}
  27. 	get_sum();
  28. 	int mx = 1e-9;
  29. 	for(int top = 1; top <= n; top++){
  30. 		for(int left = 1; left <= m; left++){
  31. 			for(int bottom = top; bottom <= n; bottom++){
  32. 				for(int right = left; right <= m; right++){
  33. 					mx = max(mx, query(top, left, bottom, right));			
  34. 				}
  35. 			}
  36. 		}
  37. 	}
  38. 	cout << mx << endl;
  39. }
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/T9jbz0
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!