思路：
考虑动态规划。
界说 \(dp_i\) 表现若有一班车在第 \(i\) 个时间出发所有人等待的时间，则状态转移方程为：
\[dp_i = dp_j + \operatorname{get}(j+1,i)(j \le i - m)\]
其中 \(\operatorname{get}(l,r)\) 表现等车时间在 \([l,r]\) 范围内的人在 \(r\) 处上车的等待时间，考虑 \(O(1)\) 求出 \(\operatorname{get}(l,r)\)。
界说 \(s_i\) 表现等车时间在 \([0,i]\) 的所有人的等车时间之和，\(a_i\) 表现等车时间在 \([0,i]\) 的人的个数，则：
\[\operatorname{get}(l,r) = r \times (a_r - a_{l-1}) - (s_r - s_{l-1})\]
此时时间复杂度优化到了 \(O(T^2)\)，考虑缩小 \(j\) 的范围。
注意到若在某时刻回来，且等待不发车时间 \(>m\) 了，肯定没有中间发一次车优，则 \(j\) 的范围应该在 \([i-2m,i-m]\)。
此时时间复杂度为 \(O(TM)\)。
完整代码：
[code]#include#define Add(x,y) (x+y>=mod)?(x+y-mod) x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);using namespace std;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=4e6+10; inline ll read(){ ll x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c |
