Submission #1300698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300698		danglayloi1	Orchard (NOI14_orchard)	C++20	25 / 25	416 ms	30772 KiB

orchard

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
int n, m, ans=inf;
vector<vector<int>> s0, s1;
vector<vector<char>> a;
int get(int x, int y, int u, int v, int k)
{
    if(k==0) return s0[u][v]-s0[x-1][v]-s0[u][y-1]+s0[x-1][y-1];
    return s1[u][v]-s1[x-1][v]-s1[u][y-1]+s1[x-1][y-1];
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    a.assign(n+2, vector<char>(m+2));
    s0.assign(n+2, vector<int>(m+2, 0));
    s1.assign(n+2, vector<int>(m+2, 0));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin>>a[i][j];
            s0[i][j]=s0[i-1][j]+s0[i][j-1]-s0[i-1][j-1]+(a[i][j]=='0');
            s1[i][j]=s1[i-1][j]+s1[i][j-1]-s1[i-1][j-1]+(a[i][j]=='1');
        }
    }
    ans=min(ans, min(s0[n][m], s1[n][m]));
    for(int l = 1; l <= n; l++)
    {
        for(int r = l; r <= n; r++)
        {
            int base[2];
            for(int j = 0; j < 2; j++)
                base[j]=get(1, 1, l-1, m, j)+get(r+1, 1, n, m, j);
            int one=0, zero=0;
            for(int i = 1; i <= m; i++)
            {
                int cur[2];
                for(int j = 0; j < 2; j++)
                    cur[j]=get(l, 1, r, i, j);
                // if(l==2 && r==4 && i==6) cout<<cur[0]<<' '<<cur[1]<<' '<<one<<'\n';
                ans=min(ans, cur[0]-one+base[1]+get(l, i+1, r, m, 1));
                one=max(one, cur[0]-cur[1]);
                zero=max(zero, cur[1]-cur[0]);
            }
        }
    }
    cout<<ans;
}

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