This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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][j - 1] + 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 <= m; ++left){
for(int right = left; right <= m; ++right){
int cur[n + 1] = {0};
for(int i = 1; i <= n; ++i)
cur[i] = pre_sum[i][right] - pre_sum[i][left - 1];
long long sum = 0, ans = 0, lptr = 1, rptr = 1, lptr_mx = 1, rptr_mx = 1;
for(int i = 1; i <= n; ++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[rptr_mx][right] - ones[lptr_mx - 1][right] - ones[rptr_mx][left - 1] + ones[lptr_mx - 1][left - 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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |