oj.uz

Submission #392963

# Submission time Handle Problem Language Result Execution time Memory
392963 2021-04-22T12:52:50 Z sumit_kk10 Orchard (NOI14_orchard) C++14
8 / 25
 1000 ms 20756 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][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;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 588 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1100 ms 20756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1096 ms 3532 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
4.0 / 4.0

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

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 9876 KB Time limit exceeded
2 Halted 0 ms 0 KB -