因为自己没有看内存限制爆掉100pts?以为自己极限数据跑的很快就稳A?
内存限制:128MB,我开了3个4000*4000的数组,成功爆掉,从AC->mle0
虽然说因为优化时间卡爆了空间,但是如果不优化也是可以A的,只能说自己没看清题。
但是这次考试发挥的还是很不错的,T1不M的话是215,很稳的rk1
而且T1我有一个非常清奇的思路,但是式子大概是一样的。
也许现在思维有了一点提升?(杂题做的跟shi一样)
T1.
题解是考虑每种斜率对于答案的贡献,我却有非常神奇的思路:考虑每个点对于答案的贡献!
为了保证不重,我们对于每个点只考虑它向它上面的所有点连线的情况。
那么分为:1.向它左上的矩形连线。2.向它右上的矩形连线。
每种情况相当于从(0,0)向一个矩形连线的情况,预处理出来就行了。
那么考虑与之前的重复:向左上连的线重复的为向右下连的线,右上同理,注意这两个东西要对上面取min。
把这个东西前缀和即可。