Submission #1113216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113216		votranngocvy	Orchard (NOI14_orchard)	C++14	25 / 25	176 ms	110020 KiB

orchard

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 5e3 + 2;
vector<vector<int>>a,pre;
vector<int>sum,suf;
int n,m,total;

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    total = 0;
    a.assign(n + 5,vector<int>(m + 5));
    pre.assign(n + 5,vector<int>(m + 5,0));
    sum.assign(m + 5,0);
    suf.assign(m + 5,0);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            char x;
            cin >> x;
            a[i][j] = x - '0';
            total += a[i][j];
            pre[i][j] = pre[i - 1][j] + 1 - a[i][j];
        }
    int ans = 1e18;
    for (int l = 1; l <= n; l++)
        for (int r = l; r <= n; r++) {
            sum[0] = 0;
            for (int i = 1; i <= m; i++)
                sum[i] = sum[i - 1] + pre[r][i] - pre[l - 1][i];
            suf[m + 1] = 1e18;
            for (int i = m; i > 0; i--)
                suf[i] = min(suf[i + 1],2 * sum[i] - (r - l + 1) * i);
            for (int i = 1; i <= m; i++)
                ans = min(ans,suf[i + 1] - 2 * sum[i - 1] + total + (r - l + 1) * (i - 1));
        }
    cout << ans << "\n";
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 5 / 5
• Subtask 4: 3 / 3
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5