Submission #837132

#	Time	Username	Problem	Language	Result	Execution time	Memory
837132		vjudge1	Orchard (NOI14_orchard)	C++17	25 / 25	155 ms	47272 KiB

orchard

#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 / 4
• Subtask 2: 4 / 4
• Subtask 3: 5 / 5
• Subtask 4: 3 / 3
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5