题目分析：
2500的题目为什么我想了这么久。。。
考虑答案是什么。对于一辆从$s$到$t$的车，它有$k$次加油的机会。可以发现实际上是将$s$到$t$的路径以城市为端点最多划分为最大长度最小的$k+1$段。不难发现这样做一定是最优的。
设计DP状态$f[i][j][k]$表示将第$i$座城市到第$j$座城市的路径划分为$k$段。朴素的DP方程是：
$$f[i][j][k] = min(max(f[i][x][k-1],a[j]-a[x])),(which)x \in [i,j]$$
这个DP是$O(n^4)$的，但我们注意到DP状态有单调性。
换句话说，存在一个城市$y$，使得任意$x<y$满足$max(f[i][x][k-1],a[j]-a[x])=a[j]-a[x]$，任意$x>y$满足$max(f[i][x][k-1],a[j]-a[x])=f[i][x][k-1]$。我们考虑的转移只有两个点是有意义的。
对于相同的$i$，$y$的选取仍然具有单调性，所以利用two pointers移动指针可以做到$O(n^3)$
注意：开三维数组会MLE，我们可以滚动一维(甚至可以滚动两维，心动不如行动，试着写一下吧)。
代码：
#include<bits/stdc++.h>
using namespace std; const int maxn = ; int n,m,a[maxn],nxt[maxn]; struct node{int s,t,oil;}; int f[maxn][maxn][];
vector <node> hh[maxn]; void read(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=m;i++){
int s,t,oil,tms;
scanf("%d%d%d%d",&s,&t,&oil,&tms);
tms = min(tms,t-s-)+;
hh[tms].push_back((node){s,t,oil});
}
} void work(){
long long ans = ;
for(int i=;i<=n;i++) for(int j=i;j<=n;j++) f[i][j][] = a[j]-a[i];
for(int k=;k<=n-;k++){
for(int i=;i<hh[k].size();i++)
ans = max(ans,1ll*f[hh[k][i].s][hh[k][i].t][k&]*hh[k][i].oil);
for(int i=;i<=n;i++){
f[i][i][(k+)&] = ; int pts = i;
for(int j=i+;j<=n;j++){
while(f[i][pts][k&] < a[j]-a[pts])pts++;
f[i][j][(k+)&] = min(f[i][pts][k&],a[j]-a[pts-]);
}
}
}
printf("%lld\n",ans);
} int main(){
read();
work();
return ;
}