oj.uz

Submission #837132

# Submission time Handle Problem Language Result Execution time Memory
837132 2023-08-25T02:10:50 Z vjudge1 Orchard (NOI14_orchard) C++17
25 / 25
 155 ms 47272 KB 
#include <bits/stdc++.h>
using namespace std;
#define futaba ios_base::sync_with_stdio(false); cin.tie(NULL);
#define rio return 0;
#define fi first
#define se second

// Fun things are fun. //

int main() {
    /* freopen(".txt", "r", stdin);
    freopen(".txt", "w", stdout); */
    futaba
    int n, m;
    cin >> n >> m;
    int a[n + 5][m + 5], prf[n + 5][m + 5];
    int cnt = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];
            if(a[i][j]) cnt++;
        }
    }
    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= m; j++) {
            prf[i][j] = 0;
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            prf[i][j] = prf[i - 1][j] + prf[i][j - 1] - prf[i - 1][j - 1];
            if(a[i][j]) prf[i][j]++;
        }
    }
    int ans = 1e9;
    for(int i = 1; i <= n; i++) {
        for(int j = i; j <= n; j++) {
            int l = 1;
            for(int k = 1; k <= m; k++) {
                int tmp = prf[j][k] - prf[j][l - 1] - prf[i - 1][k] + prf[i - 1][l - 1];
                if(2 * tmp <= (j - i + 1) * (k - l + 1)) {
                    l = k + 1;
                    continue;
                }
                ans = min(ans, cnt + ((j - i + 1) * (k - l + 1)) - 2 * tmp);
            }
        }
    }
    cout << ans << '\n';
    rio
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 2 ms 980 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 47188 KB Output is correct
2 Correct 64 ms 47188 KB Output is correct
3 Correct 65 ms 47272 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5840 KB Output is correct
2 Correct 12 ms 5716 KB Output is correct
3 Correct 12 ms 5716 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 5 ms 468 KB Output is correct
3 Correct 6 ms 468 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 6372 KB Output is correct
2 Correct 155 ms 6368 KB Output is correct
3 Correct 152 ms 6364 KB Output is correct