Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <algorithm>
- #include <vector>
- #include <string>
- #include <cstring>
- using namespace std;
- const int maxn = 2000;
- int a[maxn + 5][maxn + 5];
- int b[maxn + 5][maxn + 5];
- long long sums[maxn + 5];
- long long spLin[maxn + 5][maxn + 5];
- long long spCol[maxn + 5][maxn + 5];
- void rotateMatrix(int n, int m) {
- for (int i = 1; i <= n; ++i)
- for (int j = 1; j <= m; ++j)
- b[j][i] = a[i][j];
- for (int i = 1; i <= m; ++i)
- for (int j = 1; j <= n; ++j)
- a[i][j] = b[i][j];
- }
- int solve(int n, int m, int k) {
- memset(spLin, 0, sizeof(spLin));
- memset(spCol, 0, sizeof(spCol));
- for (int i = 1; i <= n; ++i) {
- for (int j = 1; j <= m; ++j) {
- spLin[i][j] = spLin[i][j - 1] + a[i][j];
- spCol[i][j] = spCol[i - 1][j] + a[i][j];
- }
- }
- int best_ans = n * m;
- for (int max_rem_left = 0; max_rem_left < m; ++max_rem_left) {
- int up = 0, down = 0, left = 0, right = 0;
- int ans = 0;
- while (up + down < n) {
- if (spLin[up + 1][m - right] - spLin[up + 1][left] <= k) {
- up++;
- ans++;
- } else if (spLin[n - down][m - right] - spLin[n - down][left] <= k) {
- down++;
- ans++;
- } else if (spCol[n - down][left + 1] - spCol[up][left + 1] <= k && left < max_rem_left) {
- left++;
- ans++;
- } else if (spCol[n - down][m - right] - spCol[up][m - right] <= k) {
- right++;
- ans++;
- } else {
- break;
- }
- }
- if (up + down == n)
- best_ans = min(best_ans, ans);
- }
- return best_ans;
- }
- int main() {
- // freopen("date.in", "r", stdin);
- int k, m, n;
- scanf("%d%d%d", &k, &m, &n);
- for (int i = 1; i <= n; ++i)
- for (int j = 1; j <= m; ++j)
- scanf("%d", &a[i][j]);
- int ans = solve(n, m, k);
- rotateMatrix(n, m);
- ans = min(ans, solve(m, n, k));
- printf("%d\n", ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement