Advertisement
VladNitu

miriLawnMawer

Feb 12th, 2024
1,030
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.10 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <string>
  5. #include <cstring>
  6.  
  7. using namespace std;
  8.  
  9. const int maxn = 2000;
  10.  
  11. int a[maxn + 5][maxn + 5];
  12. int b[maxn + 5][maxn + 5];
  13. long long sums[maxn + 5];
  14. long long spLin[maxn + 5][maxn + 5];
  15. long long spCol[maxn + 5][maxn + 5];
  16.  
  17. void rotateMatrix(int n, int m) {
  18.     for (int i = 1; i <= n; ++i)
  19.         for (int j = 1; j <= m; ++j)
  20.             b[j][i] = a[i][j];
  21.     for (int i = 1; i <= m; ++i)
  22.         for (int j = 1; j <= n; ++j)
  23.             a[i][j] = b[i][j];
  24. }
  25.  
  26.  
  27. int solve(int n, int m, int k) {
  28.     memset(spLin, 0, sizeof(spLin));
  29.     memset(spCol, 0, sizeof(spCol));
  30.     for (int i = 1; i <= n; ++i) {
  31.         for (int j = 1; j <= m; ++j) {
  32.             spLin[i][j] = spLin[i][j - 1] + a[i][j];
  33.             spCol[i][j] = spCol[i - 1][j] + a[i][j];
  34.         }
  35.     }
  36.     int best_ans = n * m;
  37.     for (int max_rem_left = 0; max_rem_left < m; ++max_rem_left) {
  38.         int up = 0, down = 0, left = 0, right = 0;
  39.         int ans = 0;
  40.         while (up + down < n) {
  41.             if (spLin[up + 1][m - right] - spLin[up + 1][left] <= k) {
  42.                 up++;
  43.                 ans++;
  44.             } else if (spLin[n - down][m - right] - spLin[n - down][left] <= k) {
  45.                 down++;
  46.                 ans++;
  47.             } else if (spCol[n - down][left + 1] - spCol[up][left + 1] <= k && left < max_rem_left) {
  48.                 left++;
  49.                 ans++;
  50.             } else if (spCol[n - down][m - right] - spCol[up][m - right] <= k) {
  51.                 right++;
  52.                 ans++;
  53.             } else {
  54.                 break;
  55.             }
  56.         }
  57.         if (up + down == n)
  58.             best_ans = min(best_ans, ans);
  59.     }
  60.     return best_ans;
  61. }
  62.  
  63. int main() {
  64. //    freopen("date.in", "r", stdin);
  65.     int k, m, n;
  66.     scanf("%d%d%d", &k, &m, &n);
  67.     for (int i = 1; i <= n; ++i)
  68.         for (int j = 1; j <= m; ++j)
  69.             scanf("%d", &a[i][j]);
  70.  
  71.     int ans = solve(n, m, k);
  72.     rotateMatrix(n, m);
  73.     ans = min(ans, solve(m, n, k));
  74.  
  75.     printf("%d\n", ans);
  76.  
  77.     return 0;
  78. }
  79.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement