Advertisement
Guest User

Untitled

a guest
Jan 24th, 2019
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.82 KB | None | 0 0
  1. #include <fstream>
  2. #include <climits>
  3. using namespace std;
  4. ifstream cin("ciocolata.in");
  5. ofstream cout("ciocolata.out");
  6. long long matrix[500][500];
  7. int main()
  8. {
  9. int n, m, upFinal, downFinal, leftFinal, rightFinal;
  10. long long maxSum;
  11. cin >> n >> m;
  12. for (int i = 0; i < n; ++i)
  13. for (int j = 0; j < m; ++j)
  14. cin >> matrix[i][j];
  15. maxSum = matrix[0][0];
  16. for (int left = 0; left < m; ++left)
  17. {
  18. long long aux[n + 2];
  19. for (int i = 0; i < n; ++i)
  20. aux[i] = 0;
  21. for (int right = left; right < m; ++right)
  22. {
  23. for (int i = 0; i < n; ++i)
  24. aux[i] += matrix[i][right];
  25. long long maxSumK, sumK;
  26. int st = 0, dr = 0, stFinal = 0, drFinal = 0;
  27. maxSumK = sumK = aux[0];
  28. for (int i = 1; i < n; ++i)
  29. {
  30. if (aux[i] > aux[i] + sumK)
  31. {
  32. sumK = aux[i];
  33. st = dr = i;
  34. }
  35. else
  36. {
  37. ++dr;
  38. sumK+=aux[i];
  39. }
  40. if (sumK > maxSumK)
  41. {
  42. maxSumK = sumK;
  43. stFinal = st;
  44. drFinal = dr;
  45. }
  46. }
  47. if (maxSumK > maxSum)
  48. {
  49. maxSum = maxSumK;
  50. upFinal = stFinal;
  51. downFinal = drFinal;
  52. leftFinal = left;
  53. rightFinal = right;
  54. }
  55. }
  56. }
  57. cout << maxSum << "\n";
  58. cout << upFinal + 1 << " " << leftFinal + 1 << " " << upFinal + 1 << " " << rightFinal + 1 << "\n";
  59. cout << downFinal + 1 << " " << leftFinal + 1 << " " << downFinal + 1 << " " << rightFinal + 1 << "\n";
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement