BZOJ2321【BJ2011集训】星器 <物理>

Problem

【BJ2011集训】星器

$\mathrm{Time\;Limit:\;1\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

$\mathrm{Magic\;Land}$上的时间又过了若干世纪……
现在，人们谈论着一个传说：从前，他们的祖先来到了一个位于东方的岛屿，那里简直就是另外一个世界。善于分析与构造的$\mathrm{Magic\;Land}$上的人们总是不明白那里的人们是如何不借助精确的实验与计算驱动和操纵魔法。
偶然地，一个魔法使（$\mathrm{Magician}$）来到了$\mathrm{Magic\;Land}$，在临走的时候留下了一个神奇的盒子，叫做星器（$\mathrm{casket\;of\;star}$）。
虽然不知道这个盒子是做什么的，但是经过了大量的实验和计算后，人们已经清楚它的一些事实：

• 星器之中有$N\times M$个区域，可看作分成$N$行和$M$列的格子，每个区域之中有若干单位的称为“星”的对象，这个对象的最小单位已经被确定，所以，这个数量总是整数。
• 魔法使可以驱动星器中位于同一行或同一列的不相邻（有公共边的区域称为相邻的）两个区域中各1单位的“星”，使得它们分别向中心移动1格。
• 每一次使用2中的方法驱动“星”，将会产生魔力，魔法使会得到这一部分魔力。魔力的量等于这个两个区域之间所间隔的区域数。
  这样，我们可以用一个$N\times M$的数表来表示星器的状态，比如$N=2$，$M=3$时：


当星器为左图的状态时，通过操纵第一行的第$1$和$3$个区域中的“星”（加粗的数字对应的区域），变为右图所示的状态，同时，将产生$1$单位的魔力（因为这两个区域之间恰好隔了$1$个区域）。
在经过了进一步的研究之后，人们知道了这个星器最初的状态（$\mathrm{Ini}$）以及最终被他们得到时的状态（$\mathrm{Fin}$）。
你希望知道，星器最多帮助它的拥有者提供了多少的魔力。即：经过一系列上述操作由初态（$\mathrm{Ini}$）变为终态（$\mathrm{Fin}$），至多产生多少魔力。
需要注意的是，显然操作过程中每个区域内“星”的数量不能是负的，即：如果那个区域已经没有“星”了，当然就不能继续操作了。

Input

第一行包含两个正整数$N$、$M$表示星器的大小。
接下来的$N$行，每行包含$M$个自然数：$Ini_{i,j}$，描绘了初态（$Ini$）。
在一个空行后的$N$行，每行包含$M$个自然数：$Fin_{i,j}$，描绘了终态（$Fin$）。

Output

输出一个正整数，表示至多产生的魔力。

Sample Input

Sample Input #1

5 5
1 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 1 0 1 1
1 0 0 0 0
0 0 0 0 0
0 0 0 0 1
2 0 0 0 1
0 0 2 0 0
0 0 0 0 0

Sample Input #2

1 4
10 20 30 40
0 0 100 0

Sample Output

Sample Output #1

7

Explanation
唯一的一种操作方法是：
对第$5$列的两个“星”进行一次操作，产生魔力$2$；
对第$1$列的两个“星”进行两次操作，产生魔力$3+1$；
对第$4$行的两个“星”进行一次操作，产生魔力$1$；
一共产生$7$单位的魔力。
Sample Output #2

50

HINT

数据规模和约定
$40\%$的数据中$N \le 2$，如样例$2$；
$100\%$的数据中$1 \le N$，$M\le 200$，$Ini_{i,j},\ Fin_{i,j}\le 1000$。
所有数据保证了至少存在一个操作方法使得星器由初态变为终态，同时保证了初态与终态不是完全相同的。

标签：物理 势能

Solution

玄学物理题
乱搞发现答案和移动方案无关，且行列独立
一个星星的势能为它到左上角格子的距离的平方，使用一次魔法释放的魔力为在$\frac{两个星星势能和改变量}{2}$。计算$\frac{初末状态星星势能改变量之和}{2}$即可。

##Code

#include <bits/stdc++.h>
using namespace std;
typedef long long lnt;
int n, m;    lnt s1, s2;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) for (int j = 1, x; j <= m; j++)
        scanf("%d", &x), s1 += 1LL*(i*i+j*j)*x;
    for (int i = 1; i <= n; i++) for (int j = 1, x; j <= m; j++)
        scanf("%d", &x), s2 += 1LL*(i*i+j*j)*x;
    printf("%lld", (s1-s2)/2);
    return 0;
}