无比玄学的事情

今天为了学斜率优化，去做了下APIO2014的Split the Sequence。

写的时候发现凸包里面的点，x是int级别的，y是long long级别的，叉积似乎会爆long long？

于是手写了大整数乘法，然后交上去TLE了。

（一开始T是因为用了二分复杂度差，改成不二分以后还是TLE）

强行用一些黑科技卡常数卡过去了。

由于跑得太慢垫底了，于是想了解如何优化程序效率。

看到有人直接整数除法下取整，过了。

然而斜率不一定是整数，到底对不对？我构不出数据卡这个做法- -（那么这个做法是不是对的？）感觉略玄学。

还有人直接long long叉积也过了，我试了下

100000 200

10000 10000 10000 10000 10000 ...

的数据，确实A了。

依旧比较好奇为什么不会爆- -理论上叉积是10^27级别的啊？有些玄学。

然而我把程序改完以后跑的时间仍然是rank1的5倍，百思不得其解。

用了个计数器counter计数，都是3×10^7～4×10^7，然而为何我的程序慢那么多？

各种调试……

最后脑洞大开，原本我的DP数组是

f[100010][210], g[100010][210]

改成：

f[210][100010], g[210][100010]

跑的时间就是原来的1/4了！进第一页了！UPD：现在又不是第一页了

这是为什么呢？

真是无比玄学！

求各位大神解释一下以上问题（为什么叉积不会爆、为什么反一下会快那么多）

WrongAnswer的博客