Subtask 1: Ta ta đơn giản duyệt qua tất cả các cách lựa chọn tập hợp đoạn và kiểm tra điều kiện đề bài. Độ phức tạp: $O(2^S.S^2)$ với $S$ là số lượng đoạn $[l,r]$.

Subtask 2: Với $K=2$, ta có thể xây dựng tập hợp bao gồm một đoạn có độ dài $2$ hoặc hai đoạn có độ dài $1$. Duyệt qua tất cả các cách chọn tập hợp với độ phức tạp $O(N^2)$.

Subtask 3: Ta ưu tiên chọn một đoạn có độ dài $2$ hoặc hai đoạn có độ dài $1$ có giá trị chi phí lớn nhất. Sắp xếp các đoạn theo chi phí và tìm kết quả. Độ phức tạp: $O(N.log(N))$.

Subtask 4: Gọi chi phí của đoạn $[l,r]$ là $f(l,r)=|b_r-a_l|+|b_l-a_r|$. Quy hoạch động với trạng thái như sau:

Gọi $dp[i][j]$ ($1\le i\le N$, $1\le j\le K$) là chi phí lớn nhất của tập hợp đoạn từ $1$ đến $i$ có tổng độ dài các đoạn bằng $j$. Ta xây dựng công thức truy hồi sau:

$dp[i][j]=max(dp[i-1][j],dp[i-l][j-l]+f(i-l+1,i)$ với $1\le l\le j)$.

Công thức trên với ý nghĩa: Ta có thể lựa chọn giữa việc giữ nguyên trạng thái $i-1$ trước đó (không sử dụng đoạn kết thúc tại $i$) hoặc thêm một đoạn độ dài $l$ kết thúc tại $i$ vào tập hợp đã có. Đáp án của bài toán là $dp[N][K]$.

Độ phức tạp: $O(N^2.K)$.

Subtask 5: Ta có thể biến đổi cách tính chi phí như sau:

$f(l,r)=|b_r-a_l|+|b_l-a_r|=max\{-a_r+b_r-a_l+b_l,a_r+b_r-a_l-b_l,-a_r-b_r+a_l+b_l,a_r-b_r+a_l-b_l\}$

Ngoài ra, khi tính $dp[i][j]$, ta quay về so sánh giữa các giá trị $dp[i-l][j-l]$. Các giá trị này được gọi là giá trị đường chéo khi biểu diễn $dp$ thành một ma trận hai chiều. Các cặp chỉ số $(i-l,j-l)$ này có điểm chung là đều có cùng giá trị $i-j$. Từ đó, cùng với cách biến đổi biểu thức chi phí ở trên, ta có thể duy trì $4$ kiểu kết hợp $dp[i][j]-a_{i+1}+b_{i+1}$, $dp[i][j]-a_{i+1}-b_{i+1}$, $dp[i][j]+a_{i+1}+b_{i+1}$ và $dp[i][j]+a_{i+1}-b_{i+1}$.

Khi đó, để tính $dp[i][j]$ nếu lựa chọn thêm một đoạn độ dài $l$, ta chỉ cần tìm giá trị lớn nhất trong số $4$ cách kết hợp trên.

Độ phức tạp: $O(N.K)$