oj.uz

Submission #837131

# Submission time Handle Problem Language Result Execution time Memory
837131 2023-08-25T02:06:49 Z vjudge1 Orchard (NOI14_orchard) C++17
17 / 25
 168 ms 6560 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 a[155][5005], prf[155][5005];

int main() {
    /* freopen(".txt", "r", stdin);
    freopen(".txt", "w", stdout); */
    futaba
    int n, m;
    cin >> n >> m;
    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 = 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 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

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

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 6560 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 1128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1108 KB Output is correct
2 Correct 6 ms 1704 KB Output is correct
3 Correct 6 ms 1620 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 6192 KB Output is correct
2 Correct 158 ms 6092 KB Output is correct
3 Correct 168 ms 6188 KB Output is correct