发现时间并不重要,不妨设 TT 为离散化之后最大的时间。

设在 [i,j][i,j] 中有 wi,jw_{i,j} 个活动被包含,容易 O(n3)O(n^3) 求解。

fi,jf_{i,j} 表示 [1,i][1,i] 的时间中有 jj 个活动在第 11 个场地举行,第 22 个场地举行活动的最大值。

那么有转移方程:

fi,j=maxk=1i1(fk,j+wk,i,fk,jwk,i)f_{i,j}=\max\limits_{k=1}^{i-1}(f_{k,j}+w_{k,i},f_{k,j-w_{k,i}})

gi,jg_{i,j} 表示 [i,T][i,T] 的时间中有 jj 个活动在第 11 个场地举行,第 22 个场地举行活动的最大值。

同理,有转移方程:

gi,j=maxk=i+1T(gk,j+wk,i,gk,jwk,i)g_{i,j}=\max\limits_{k=i+1}^T(g_{k,j}+w_{k,i},g_{k,j-w_{k,i}})

预处理的时间复杂度为 O(n3)O(n^3)

那么第 11 问的答案就显然是:maxj=1nmin(fT,j,j)\max\limits_{j=1}^n\min(f_{T,j},j)

下面考虑固定一个活动的情况。

显然可以得到这个区间的左右端点 L,RL,R,那么枚举前后第 11 个场地分别举办了多少比赛:

AnsL,R=maxx=0w1,Lmaxy=1wR,Tmin(x+wL,R+y,fL,x+gR,y)Ans_{L,R}=\max\limits_{x=0}^{w_{1,L}}\max\limits_{y=1}^{w_{R,T}}\min(x+w_{L,R}+y,f_{L,x}+g_{R,y})

发现如果固定 ii,那么fi,jf_{i,j}gi,jg_{i,j} 的值随 jj 的值减增大而减小,所以当 ii 增加时 jj 应该尽可能的减少。

考虑维护双指针,那么时间复杂度为 O(n3)O(n^3)