AlexNeagu11

Untitled

Feb 23rd, 2024
41
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.51 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. ifstream in("tort.in");
  8. ofstream out("tort.out");
  9.  
  10. #define cin in
  11. #define cout out
  12.  
  13. const int nax = 505;
  14. int pre[nax][nax];
  15.  
  16. int getSum(int x1, int y1, int x2, int y2) {
  17. return pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1];
  18. }
  19.  
  20. int main() {
  21. ios_base::sync_with_stdio(false);
  22. cin.tie(0);
  23.  
  24. int n, m, k;
  25. cin >> n >> m >> k;
  26. for (int i = 1; i <= n; ++i) {
  27. for (int j = 1; j <= m; ++j) {
  28. cin >> pre[i][j];
  29. pre[i][j] += pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
  30. }
  31. }
  32.  
  33. int bestSum = 1e9;
  34. int countBest = 0;
  35.  
  36. for (int w = 0; w <= k; ++w) {
  37. int h = k - w;
  38. // what remains? n - w && m = h
  39. int rN = n - w;
  40. int rM = m - h;
  41. for (int i = 1; i <= n; ++i) {
  42. for (int j = 1; j <= m; ++j) {
  43. int nxtX = i + rN - 1;
  44. int nxtY = j + rM - 1;
  45. if (nxtX > n || nxtY > m) {
  46. continue;
  47. }
  48. int curSum = getSum(i, j, nxtX, nxtY);
  49. if (curSum < bestSum) {
  50. bestSum = curSum;
  51. countBest = 1;
  52. }
  53. else if (curSum == bestSum) {
  54. countBest++;
  55. }
  56. }
  57. }
  58. }
  59.  
  60. cout << pre[n][m] - bestSum << '\n' << countBest << '\n';
  61. return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment