前缀和

https://www.programmercarl.com/kamacoder/0044.%E5%BC%80%E5%8F%91%E5%95%86%E8%B4%AD%E4%B9%B0%E5%9C%9F%E5%9C%B0.html

CPP

#include<iostream>
#include<vector>
#include <climits>
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> arr(n,vector<int>(m,0));
    int sum = 0;
    for(int i = 0;i<n;i++){
        for(int j =0;j<m;j++){
            cin>>arr[i][j];
            sum += arr[i][j];
        }
    }
    
    vector<int> horizon(n,0);
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            horizon[i] += arr[i][j];
        }
    }
    
    vector<int> vert (m,0);
    
    for(int j = 0;j<m;j++){
        for(int i = 0;i<n;i++){
            vert[j] += arr[i][j];
        }
    }
    
    int res  = INT_MAX;
    int horizoncut = 0;
    for(int i = 0;i<n;i++){
        horizoncut += horizon[i];
        res = min(res, abs(sum - horizoncut -horizoncut));
    }
    
    int vertcut = 0;
    for(int j = 0;j<m;j++){
        vertcut += vert[j];
        res = min(res ,abs(sum - vertcut -vertcut));
    }
    
    cout<<res<<endl; 
}