Submission #392966

#	Time	Username	Problem	Language	Result	Execution time	Memory
392966		sumit_kk10	Orchard (NOI14_orchard)	C++14	25 / 25	225 ms	24760 KiB

orchard

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define ld long double
using namespace std;
const int N = 1e6 + 5;
const int MOD = 1e9 + 7;

int main(){
    fast;
    int n, m;
    cin >> n >> m;
    int total = 0, pre_sum[n + 1][m + 1], ones[n + 1][m + 1];
    char b[n + 1][m + 1];
    int a[n + 1][m + 1];
    memset(pre_sum, 0, sizeof pre_sum);
    memset(ones, 0, sizeof ones);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            cin >> b[i][j];
            a[i][j] = (b[i][j] == '1' ? 1 : -1);
            pre_sum[i][j] = pre_sum[i - 1][j] + a[i][j];
            total += (a[i][j] == 1);
            ones[i][j] = ones[i - 1][j] + ones[i][j - 1] - ones[i - 1][j - 1] + (a[i][j] == 1);
        }
    }
    int res = INT_MAX;
    for(int left = 1; left <= n; ++left){
        for(int right = left; right <= n; ++right){
            int cur[m + 1] = {0};
            for(int i = 1; i <= m; ++i)
                cur[i] = pre_sum[right][i] - pre_sum[left - 1][i];
            long long sum = 0, ans = 0, lptr = 1, rptr = 1, lptr_mx = 1, rptr_mx = 1;
            for(int i = 1; i <= m; ++i){
                sum += cur[i];
                rptr = i;
                if(sum > ans){
                    ans = sum;
                    lptr_mx = lptr;
                    rptr_mx = rptr;
                }
                else if(sum < 0){
                    sum = 0;
                    lptr = i + 1;
                }
            }
            int breadth = right - left + 1, length = rptr_mx - lptr_mx + 1;
            int area = length * breadth;
            int one = ones[right][rptr_mx] - ones[left - 1][rptr_mx] - ones[right][lptr_mx - 1] + ones[left - 1][lptr_mx - 1];
            // if(left == 1 and right == 1) cout << one << '\n';
            int ok = area - one + total - one;
            if(res > ok){
                // cout << lptr_mx << ' ' << left << ' ' << rptr_mx << ' ' << right << ' ' << ok << '\n';
                res = ok; 
            }
        }
    }
    cout << res << '\n';
    return 0;
}

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