Để dễ hình dung hơn, với mỗi truy vấn có các tham số $s,f,c,r$, ta sẽ hiểu là cần xây dựng một dãy $a_{p_1}, a_{p_2}, a_{p_3}, ... ,a_{p_{r+1}}$, với dãy $p$ không giảm và $p_1 = s$ và $p_{r+1} = f$, sao cho $val = max (a_{p_i}-a_{p_{i-1}})$ là bé nhất.

Kết quả của truy vấn sẽ chính là $val*c$. Như vậy kết quả của bài toán sẽ là $max(val*c)$ với mọi truy vấn.
# Subtask 1
- Ta sẽ dùng phương pháp chặt nhị phân kết quả để tìm giá trị $val$ .
- Với mỗi giá trị $mid$, ta có thể kiểm tra xem nó có thỏa mãn không bằng cách xuất phát từ $a_s$, đi đến một vị trí $i$ sao cho $i$ lớn nhất, $i > s$ và $a_i - a_s \le mid$. Ta tính đây là một lần **dừng lại**. Sau đó, ta lại xuất phát từ $i$ và lặp lại hành động tương tự. Nếu ta có thể đi tới được $f$ mà không cần **dừng lại** quá $r$ lần, giá trị $mid$ sẽ thỏa mãn.
- Như vậy, ta có thể chặt nhị phân để tìm $val$ nhỏ nhất thỏa mãn.
- Độ phức tạp $O(n*log)$ cho **một** truy vấn.

# Subtask 3
- Tuy lần này, $n \le 400$, nhưng $m$ lại rất lớn, lên tới $5*10^5$ nên một thuật toán như $subtask$ $1$ sẽ không thể chạy.
- Ta cần sử dụng kĩ thuật quy hoạch động cho bài toán này. Gọi $dp(l,r,k)$ là kết quả tối ưu (giá trị $val$) cho đoạn $[l,r]$ nếu ta chỉ được dừng lại $k$ lần. Như vậy, với mỗi truy vấn ta sẽ lấy kết quả với $max (c*dp(s,f,r))$.
- Ta có công thức quy hoạch động như sau: $dp(l,r,k) = min(max(dp(l,x,k-1),a[r]-a[x]))$, với $x \in [l,r-1]$.
- Như vậy ta sẽ thu về thuật toán có độ phức tạp $O(n^4)$, chỉ đủ để qua $subtask$ $2$.
- Đến đây ta cần tối ưu công thức này như sau:
- Gọi $optimize(l,r,k) = x$ là vị trí tốt nhất mà $dp(l,r,k) = max (dp(l,x,k-1),a[r]-a[x])$ đạt $min$.
- Ta có nhận xét rằng $optimize(l,r,k) \le optimize(l,r+1,k)$.
- Mặt khác, ta có $dp(l,r,k) = min (max (dp(l,x,k-1),a[r]-a[x]))$, mà $dp(l,x,k-1) \le dp (l,x+1,k-1)$, đồng thời $a[r] - a[x] > a[r] - a[x+1]$ và hàm $y = max (dp(l,x,k-1),a[r]-a[x])$ sẽ có dạng giảm dần xuống đáy với từng giá trị $x$ rồi sau khi chạm đáy giá trị sẽ tăng dần. Như vậy, ta chỉ cần tăng $x$ tới khi nào $max (dp(l,x,k-1),a[r]-a[x])$ chạm đáy.
- Vậy ta có thể thực hiện thuật toán $2$ con trỏ để tính được mảng $optimize$ song song với việc tính mảng $dp$.
- Từ đó ta thu được thuật toán $O(n^3)$.
- Tuy vậy, ta cần tối ưu hóa bộ nhớ, dễ thấy ta không cần lưu chiều $l$ của $dp(l,r,k)$, đồng thời không cần lưu mảng $optimize$. Từ đó bộ nhớ giảm xuống còn $N^2$.

Code:

#include<iostream>
#include<vector>
using namespace std;
const int N = 405;
const int M = 1e5+5;
int d[N][N];
int n,m;
int a[M];
long long res = 0;
struct qr {
	int f,c,r;
};
vector<qr> v[N];
namespace sub1 {
	int s,f,c,r;
	bool check (int mid) {
		int res = 0;
		int st = s;
		for (int i=s; i<=f; i++) {
			int j = i;
			while (j < f && a[j+1]-a[i] <= mid) {
				j++;
			}
			if (j == i) return false;
			i = j-1;
			res++;
			if (j == f) break;
		} res--;
		return res <= r;
	}
	void solve () {
		for (int i=1; i<=n; i++) cin >> a[i];
		cin >> s >> f >> c >> r;
		long long lef = 0, rig = 1e9, res = 1e9;
		while (rig >= lef) {
			int mid = (rig+lef) >> 1;
			if (check(mid)) res = mid, rig = mid - 1;
			else lef = mid + 1;
		}
		cout << 1ll*res*c << '\n';
	}
}
void cal () {
	for (int l=1; l<=n; l++) {
		for (int r=l; r<=n; r++) {
			d[r][0] = a[r] - a[l];
		}
		for (int k=1; k<=n; k++) {
			int opt = l;
			for (int r=l; r<=n; r++) {
				while (opt < r && max (d[opt][k-1],a[r]-a[opt]) >= max (d[opt+1][k-1],a[r]-a[opt+1])) {
					opt++;
				}
				d[r][k] = max (d[opt][k-1],a[r]-a[opt]);
			}
		}
		for (auto val : v[l]) {
			int f = val.f, c = val.c, r = val.r;
			res = max (res,1ll*d[f][r]*c);
		}
	}
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	if (m == 1) {
		sub1::solve();
		return 0;
	}
	for (int i=1; i<=n; i++) {
		cin >> a[i];
	}
	for (int i=1; i<=m; i++) {
		int s,f,c,r;
		cin >> s >> f >> c >> r;
		v[s].push_back({f,c,r});
	}
	cal();
	cout << res;
}