oj.uz

Submission #124757

# Submission time Handle Problem Language Result Execution time Memory
124757 2019-07-03T21:15:01 Z AdOjis485 Orchard (NOI14_orchard) C++14
25 / 25
 330 ms 39552 KB 
//
//  main.cpp
//  orchard
//
//  Created by Ema Skottova on 03.07.19.
//  Copyright © 2019 AdOjis485. All rights reserved.
//

#include <iostream>
#include <vector>
#define int int64_t
using namespace std;

signed main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> ps(n + 1, vector<int> (m + 1));
    vector<vector<int>> ps2(n + 1, vector<int> (m + 1));
    int sum = 0;
    for(int i = 1; i <= n; i ++){
        int row = 0;
        for(int j = 1; j <= m; j ++){
            int x;
            cin >> x;
            ps2[i][j] = 2 * x - 1 + ps2[i - 1][j] + ps2[i][j - 1] - ps2[i - 1][j - 1];
            ps[i][j] = x + row + ps[i - 1][j];
            row += x;
            sum += x;
        }
    }
    int mi = n * m;
    /*cout << "\n";
    for (auto a : ps) {for (auto i : a) cout << i << " "; cout << "\n";}
    cout << "\n";*/
    for(int i1 = 1; i1 <= n; i1 ++){
        for(int i2 = 0; i2 < i1; i2 ++){
            int min2 = 0;
            int max2 = 0;
            int j1 = 0;
            int j2 = 0;
            int j3 = 0;
            for(int j = 0; j <= m; j ++){
                int value = ps2[i1][j] - ps2[i1][0] - ps2[i2][j] + ps2[i2][0];
                if(value < min2){
                    min2 = value;
                    j3 = j;
                }
                if(value - min2 > max2){
                    max2 = value - min2;
                    j1 = j;
                    j2 = j3;
                }
            }
            //cout << i2 << ' ' << i1 << ' ' << j2 << ' ' << j1 << '\n';
            int rect_area = (i1 - i2) * (j1 - j2);
            int ones_inside = ps[i1][j1] - ps[i1][j2] - ps[i2][j1] + ps[i2][j2];
            int zeros_inside = rect_area - ones_inside;
            //int outside_area = n * m - rect_area;
            int ones_outside = sum - ones_inside;
            //int zeros_outside = outside_area - ones_outside;
            int zero_one = zeros_inside + ones_outside;
            //int one_zero = ones_inside + zeros_outside;
            mi = min(mi, zero_one);
        }
    }
    cout << mi << '\n';
    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 39508 KB Output is correct
2 Correct 304 ms 39552 KB Output is correct
3 Correct 304 ms 39520 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 5736 KB Output is correct
2 Correct 60 ms 5864 KB Output is correct
3 Correct 59 ms 5860 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 13 ms 636 KB Output is correct
3 Correct 13 ms 760 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 12228 KB Output is correct
2 Correct 309 ms 12224 KB Output is correct
3 Correct 317 ms 12280 KB Output is correct