牛客 NC202492 仓库选址

题目链接：https://ac.nowcoder.com/acm/problem/202492

代码：

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int s[N][N];

int get(int x1, int y1, int x2, int y2)
{
    return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
}

int main()
{
    int T;
    scanf("%d", &T);
    
    while (T--)
    {
        int n, m; // m行n列
        scanf("%d%d", &n, &m);
        
        int sum = 0;
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                int x;
                scanf("%d", &x);
                sum += (i - 1 + j - 1) * x;
                s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + x;
            }
        }
        
        int res = INF;
        for (int i = 1; i <= m; i++)
        {
            int t = sum;
            for (int j = 1; j <= n; j++)
            {
                res = min(res, t);
                t += get(1, 1, m, j) - get(1, j + 1, m, n);
            }
            sum += get(1, 1, i, n) - get(i + 1, 1, m, n);
        }
        
        printf("%d\n", res);
    }
    
    return 0;
}