ACM2016_North_G – Optimal division (ACM 2016 Miền Bắc)

1. Đề thi ACM 2016 Miền Bắc

Byteland là một xứ sở rất đẹp và yên bình. Ban đầu, vua Byteland đã chia vùng đất của mình thành m hàng và n cột, giao điểm của hàng thứ i và cột thứ j được gọi là tỉnh ij với dân số Pij. Sau đó, nhận thấy rằng chia quá nhiều tỉnh sẽ dẫn tới sự khác biệt về văn hóa, kinh tế nên nhà vua quyết định chia lại vương quốc thành 4 tỉnh. Nhà vua thực hiện việc này bằng cách chia đất theo một đường ngang và một đường dọc (chạy theo ranh giới của các tỉnh cũ).

Nhà vua không muốn có sự khác biệt dân số quá lớn nên ngài yêu cầu bạn tìm ra cách chia sao cho tỉnh đông dân nhất và tỉnh thưa dân nhất có sự chênh lệch dân số thấp nhất.

Dữ liệu đầu vào

– Dòng đầu tiên là 2 số nguyên m, n;  (2<=m<=1000, 2<=m<=1000)
– m dòng tiếp theo, mỗi dòng gồm n số liệu là dân số các tỉnh trước khi chia (không quá 1000)

Dữ liệu đầu ra

Độ chênh lệch dân số ít nhất giữa tỉnh đông dân nhất và tỉnh thưa dân nhất

Ví dụ

• input
  2 2
  1 2
  3 4
  
  output
  3
  

• input
  3 3
  1 1 9
  1 1 1
  8 1 1
  output
  9

2. Code Tham khảo ACM 2016 Miền Bắc

#include <iostream>
#include <climits>
#include <cmath>
using namespace std;
const int nmax = 1010;

long a[nmax][nmax], n, m, res = LONG_MAX, tmp, gtmin, gtmax;

inline long get(int i, int j, int u, int v)
{
    return a[u][v]-a[i-1][v]-a[u][j-1]+a[i-1][j-1];
}

int main()
{
    cin >> m >> n;
    for (int i=0; i<=m+1; i++)
        a[i][0]=0;
    for (int j=0; j<=n+1; j++)
        a[0][j]=0;

    for (int i = 1; i<=m; i++)
        for (int j=1; j<=n; j++)
            cin >> a[i][j];

    for (int i = 1; i<=m; i++)
        for (int j=1; j<=n; j++)
            a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];

    for (int i = 1; i<=m-1; i++)
        for (int j=1; j<=n-1; j++)
        {
            tmp = get(1,1,i,j); // tren trai
            gtmin = tmp;
            gtmax = tmp;
            tmp = get(1,j+1,i,n); // tren phai
            gtmin = min(gtmin, tmp);
            gtmax = max(gtmax, tmp);
            tmp = get(i+1,1,m,j); // duoi trai
            gtmin = min(gtmin, tmp);
            gtmax = max(gtmax, tmp);
            tmp = get(i+1,j+1,m,n); // duoi phai
            gtmin = min(gtmin, tmp);
            gtmax = max(gtmax, tmp);
            res = min(res,(long)abs(gtmin-gtmax));
        }
    cout << res;
    return 0;
}