#01: ---|---|---|---|---|---|---|---|-

Accepted (0ms, 52456KB)

#02: ---|---|---|---|---|---|---|---|-

Accepted (0ms, 52456KB)

#03: ---|---|---|---|---|---|---|---|-

Accepted (0ms, 52456KB)

#04: ---|---|---|---|---|---|---|---|-

Accepted (1617ms, 52456KB)

#05: ---|---|---|---|---|---|---|---|-

Accepted (0ms, 52456KB)

#06: ---|---|---|---|---|---|---|---|-

Accepted (0ms, 52456KB)

#07: ---|---|---|---|---|---|---|---|-

Accepted (0ms, 52456KB)

#08: ---|---|---|---|---|---|---|---|-

Accepted (684ms, 52456KB)

#09: ---|---|---|---|---|---|---|---|-

Accepted (715ms, 52456KB)

#10: ---|---|---|---|---|---|---|---|-

Accepted (653ms, 52456KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 3671ms / 52456KB

总算AC了 我做这题从40分到60分到90分再到100分花了将近3小时，最大的好处就是买了个教训：写快排时第一关键数组与第二关键数组要分开写，不要怕麻烦。我就是因为一起写了导致有一个点一直没过。

var

n,m,i,j,ki,kj,xi,yi,st,en,ans,uu:longint;

a,g:array[0..1000,0..1000]of longint;

sum,f,h:array[0..1000,0..1000]of int64;

t:array[1..1000]of longint;

b:array[1..1000000]of int64;

x,y,q:array[1..1000000]of longint;

used:array[1..1000,1..1000]of boolean;

kq,aa,bb:int64;

function max(x,y:longint):longint;

begin

if x

├ 测试数据 01：答案正确... (0ms, 98348KB) 

├ 测试数据 02：答案正确... (0ms, 98348KB) 

├ 测试数据 03：答案正确... (0ms, 98348KB) 

├ 测试数据 04：答案正确... (0ms, 98348KB) 

├ 测试数据 05：答案正确... (0ms, 98348KB) 

├ 测试数据 06：答案正确... (0ms, 98348KB) 

├ 测试数据 07：答案正确... (0ms, 98348KB) 

├ 测试数据 08：答案正确... (903ms, 98348KB) 

├ 测试数据 09：答案正确... (918ms, 98348KB) 

├ 测试数据 10：答案正确... (887ms, 98348KB) 

fp

碉堡爆了，读取MN（弱爆了），求和3次MN（弱爆了）,求最小值单调队列3次MN（弱爆了）。

统计点和删点（（M-a)（N-b））（弱爆了）排序（M-a)（N-b）lg(M-a)（N-b））

4MN复杂度是如何做到的求解。

---|->碉堡，这道题p能1000ms内解决，估计C++党500ms无压力。时限可以设定1s了。。

---|>wzf

贴代码的自重……自重……

第4个点无道理1600+ms啊，后3点的ms倒是控制的非常优秀，膜拜

├ 测试数据 01：答案正确... (0ms, 94716KB) 

├ 测试数据 02：答案正确... (0ms, 94716KB) 

├ 测试数据 03：答案正确... (0ms, 94716KB) 

├ 测试数据 04：答案正确... (0ms, 94716KB) 

├ 测试数据 05：答案正确... (0ms, 94716KB) 

├ 测试数据 06：答案正确... (0ms, 94716KB) 

├ 测试数据 07：答案正确... (0ms, 94716KB) 

├ 测试数据 08：答案正确... (1106ms, 94716KB) 

├ 测试数据 09：答案正确... (1090ms, 94716KB) 

├ 测试数据 10：答案正确... (1028ms, 94716KB) 

先求出以每个点为左上角的矩形的最少代价

为此我们需要2个值

1:以该点为左上角的矩形的权和

{这个我比较龊~，我是先求出行列的前缀和 然后加加减减 画图易得 复杂度N^2}

2:以该点为左上角的矩形中的最小权值

(这个我也很龊，两次单调队列找最小值 复杂度n^2)

(其实这两步都可以用N^3的算法 貌似数据比较弱一点 我之前的N^3也过了 用时最长的一个点式1400MS左右。。。)

这样代价就可以表示为:i,j矩形的权和-a*b*ij矩形中的最小值

然后以代价、坐标什么的作为关键字 进行快排

然后按顺序去取最小的矩形

每取完一个后 删掉会与之冲突的其他矩形的起点!!

就是说如果以那些点为起点的矩形一定会与它冲突 所以一定要被标记为删除

也要保证 不多删 不少删

这样一直取知道完……

貌似有点复杂……

交了10遍左右，终于不TLE了。。。

对于P党，qsort中的比较不要写成函数，这样可以节省大量时间，从TLE降到10xx ms。。。

OrzLJL，CSZ两位神犇！

不好意思，由于没删除调试用的输出和Qsort写挫了，交了3次才a……拖大家后腿了

另外@CSZ神犇，你Qsort是线性的？

完全看不懂csz神犇的删除于是我写了双向链表。

完全看不懂csz的预处理，所以我开了N+1个单调队列。

完全看不懂csz的部分和，于是我维护（1,1）到（i，j）的和然后容斥。

于是——————

测试数据 08：答案正确... (1450ms, 47684KB) 

差一点就T了！！！

我排序O((N-A)(M-B)log((N-A)(M-B))),而且有比较函数，常数比较大。

整个预处理(最小值和求和)应该是O((N-A)(M-B))

不好意思，由于没注意数据规模，交了3次才a……拖大家后腿了

单调队列预处理，排序，删点，可证明每个点最多被删4次，复杂度为O(4NM),可秒