Submission #124754

#	Time	Username	Problem	Language	Result	Execution time	Memory
124754		AdOjis485	Orchard (NOI14_orchard)	C++14	21 / 25	316 ms	39524 KiB

orchard

//
//  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: 0 / 4
• Subtask 2: 4 / 4
• Subtask 3: 5 / 5
• Subtask 4: 3 / 3
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5