T574960 「PA Mashup #2」领地

一个长为 $X$ 宽为 $Y$ 的矩形被分为 $X\times Y$ 个方格。我们记第 $i$ 行第 $j$ 列的方格为 $(i,j)$。 有 $n$ 种动物。第 $i$ 种动物**不喜欢**待在以 $(x_i,y_i)$ 和 $(x_i',y_i')$ 为对角顶点确定的矩形内。我们保证这个矩形**严格包含于** $X\times Y$ 的矩形。 第 $i$ 种动物有 $c_i$ 只。那么，一共有 $S=c_1+c_2+\cdots+c_n$ 只动物。 现在要将每只动物放在一个方格里面。**一个方格里面可以放多只动物，但是一只动物不能待在它不喜欢的区域**。 记 $(i,j)$ 内有 $p_{i,j}$ 只动物，那么这种分配方式的得分为 $\displaystyle \sum_{1\le i\le X}\sum_{1\le j\le Y} {p_{i,j}\choose 2}$。这里，$\displaystyle {a\choose 2}=\frac{a(a-1)}{2}$。 找到合法的分配方式中得分最大的那个分配方式。只需要输出最大的得分。

无

无

- $1\le n\le 10^5$； - $1\le X,Y\le 10^3$； - $\textcolor{red}{1\le x_i\le x'_i\le X},\textcolor{red}{1\le y_i\le y'_i\le Y}$； - 以下条件中，**至少有一个**成立：${x_i\neq 1},{y_i\neq 1},{x'_i\neq X},{y'_i\neq Y}$； - $1\le c_i\le 10^3$。 样例解释： 对于第一个样例，只能把第一种动物全部放在 $(1,2)$，第二种动物全部放在 $(1,1)$，得分为 $\binom{4}{2}+\binom{3}{2}=9$。 对于第二个样例，最优方案为把三种动物都全部放在 $(4,1)$，得分为 $\binom{3}{2}=3$。容易证明没有比其更优的答案。