oj.uz

Submission #392966

# Submission time Handle Problem Language Result Execution time Memory
392966 2021-04-22T13:06:18 Z sumit_kk10 Orchard (NOI14_orchard) C++14
25 / 25
 225 ms 24760 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 24760 KB Output is correct
2 Correct 52 ms 24668 KB Output is correct
3 Correct 49 ms 24660 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3916 KB Output is correct
2 Correct 9 ms 4044 KB Output is correct
3 Correct 10 ms 3916 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 8 ms 600 KB Output is correct
3 Correct 10 ms 588 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 9904 KB Output is correct
2 Correct 183 ms 9900 KB Output is correct
3 Correct 225 ms 9896 KB Output is correct