OLP MTTN 2022 - Vòng Chung kết - Bảng Chuyên Tin

Thời gian rảnh Thuận thường hướng dẫn các em nhỏ học lập trình, dưới đây là một bài toán rèn luyện kĩ năng cũng như tư duy lập trình.

Cho một dãy số nguyên dương \(a_1, a_2, ..., a_n (1 < a_i \le 10^9)\) và số nguyên dương \(t (1 \le t \le 3)\). Gọi \(s_1, s_2, s_3\) tương ứng là số bộ chỉ số \(1 \le i < j < k \le n\) mà \(a_i, a_j, a_k\) là ba cạnh của một tam giác nhọn, tam giác vuông, tam giác tù. Hãy tính giá trị \(s_t\).

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

• Dòng đầu chứa hai số nguyên dương \(n, t\);
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, ..., a_n\).

Output

• Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là giá trị \(s_t\) tính được.

Scoring

• Subtask #1 (\(30\%\) số điểm): \(n = 3\) và 10% cho từng giá trị của \(t\);
• Subtask #2 (\(30\%\) số điểm): \(n \le 300\) và 10% cho từng giá trị của \(t\);
• Subtask #3 (\(40\%\) số điểm): \(n \le 3000\)

Example

3 2
3 4 5

1

4 1
3 4 5 6

1

Thành phố Thuận ở được biểu diễn bằng một bảng hai chiều kích thước \(m\times n\). Các hàng của bảng được đánh số từ đến từ trên xuống dưới, các cột của bảng được đánh số từ \(1\) đến \(n\) từ trái sang phải. Khu vực dân cư nằm giao giữa hàng \(i\) và cột \(j\) được gọi là khu vực dân cư \((i, j)\).

Hiện tại có \(k\) siêu thị đang hoạt động, siêu thị thứ \(t (1 \le t \le k)\) sẽ phục vụ các khu vực dân cư nằm trong hình chữ nhật có ô trái trên là khu vực dân cư \((x_t, y_t)\) và ô phải dưới là khu vực dân cư \((u_t, v_t)\). Theo phân tích đánh giá, dân cư một khu vực sẽ hạnh phúc nếu khu vực đó có đúng \(s\) siêu thị phục vụ. Thuận dự định mở một siêu thị, siêu thị cũng sẽ phục vụ các khu vực dân cư nằm trong một hình chữ nhật, Thuận mong muốn số lượng khu vực dân cư có đúng \(s\) siêu thị phục vụ là nhiều nhất.

Yêu cầu: Hãy giúp Thuận xác định một hình chữ nhật là khu vực mà siêu thị của Thuận sẽ phục vụ để số lượng khu vực dân cư có đúng \(s\) siêu thị phục vụ là nhiều nhất.

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

• Dòng thứ nhất chứa bốn số nguyên dương \(m, n, k\) và \(s (1 \le s \le k \le 10^{15})\)
• Dòng thứ \(t (1 \le t \le k)\) trong \(k\) dòng tiếp theo chứa \(4\) số nguyên dương \(x_t, y_t, u_t, v_t (1 \le x_t \le u_t \le m; 1 \le y_t \le v_t \le n)\)

Output

• Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là số lượng khu vực dân cư có đúng \(s\) siêu thị phục vụ là nhiều nhất.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(m, n \le 20\);
• Subtask \(2\) (\(30\%\) số điểm): \(m, n \le 80\);
• Subtask \(3\) (\(30\%\) số điểm): \(m, n \le 400\)

Example

3 4 3 2
1 1 1 4
2 2 3 3
2 3 3 4

8

1 1 1 1
1 1 1 1

0

Ngoài các kiến thức học trên trường, Thuận nhận thấy mình còn thiếu nội dung kiến thức. Qua tìm hiểu Thuận biết rằng, để bổ sung nội dung kiến thức thứ \(i (1 \le i \le n)\) , Thuận cần tham gia khóa học với chi phí là \(c_i\). Thuận đang dự định làm sản phẩm, sản phẩm thứ \(j (1 \le j \le m)\) sẽ đòi hỏi kiến thức sau:
\(s_{j_1}, s_{j_2}, ..., s_{j_{p_j}}\) (1 \le \(s_{j_1} < s_{j_2} < ... < s_{j_{p_j}} \le n\)) và nếu hoàn thành xong sản phẩm này Thuận sẽ bán và thu về được số tiền là \(t_j\) .Sắp tới, Thuận sẽ đăng kí học một số khóa học (hoặc không đăng kí học khóa học nào) và với các kiến thức mới đó Thuận sẽ làm tất các sản phẩm có thể làm được.

Yêu cầu: Gọi \(X\) là tổng chi phí tham gia các khóa học, \(Y\) là tổng tiền thu được từ các sản
phẩm mà Thuận có thể làm được, hãy giúp Thuận đăng kí các môn học để \(|Y - X|\) đạt giá trị
lớn nhất.

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

• Dòng đầu chứa hai số nguyên dương \(n, m\);
• Dòng thứ hai gồm \(n\) số nguyên \(c_1, c_2, ..., c_n (1 \le c_i \le 10^6)\);
• Dòng thứ \(j (1 \le j \le m)\) trong \(m\) dòng tiếp theo mô tả thông tin về sản phẩm thứ \(j\) có khuôn dạng:
  • Đầu tiên là số nguyên \(t_j (t_j \le 10^6)\);
  • Tiếp theo là số nguyên \(p_j\);
  • Tiếp theo là \(p_j\) số nguyên \(s_{j_1}, s_{j_2}, ..., s_{j_{p_j}}\)

Output

• Ghi ra thiết bị ra chuẩn một số nguyên là giá trị \(Y - X\) lớn nhất tìm được.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 20\) và \(m \le 100\);
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 100\) và \(m \le 20\);
• Subtask \(3\) (\(30\%\) số điểm): \(n, m \le 100\) và \(p_j = 2\);
• Subtask \(4\) (\(30\%\) số điểm): \(n, m \le 1000\).

Example

3 3
1 2 3
2 2 1 3
5 2 1 3
1 1 2

3

3 3
3 3 3
1 2 1 2
1 2 1 3
1 1 2

0

Khi nghiên cứu về lý thuyết đồ thị, Thuận đã tìm ra một đặc trưng cho cây. Cụ thể, với cây
gồm \(n\) đỉnh, đỉnh \(i (1 \le i \le n)\) có trọng số là \(w[i]\), gọi \(f(i, j)\) là độ mất cân bằng giữa hai
đỉnh \(i\) và \(j (1 \le i, j \le n)\), trọng số \(f(i, j)\) được tính bằng chênh lệnh trọng số giữa đỉnh có
trọng số lớn nhất với đỉnh có trọng số bé nhất trong các đỉnh nằm trên đường đi từ \(i\) đến \(j\)
(bao gồm cả \(i, j\)). Độ mất cân bằng \(T\) của cây là tổng độ mất cân bằng giữa mọi cặp đỉnh.

Yêu cầu: Cho một cây và trọng số các đỉnh, hãy tính giá trị \(T\).

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

• Dòng đầu chứa số nguyên dương \(n\);
• Dòng thứ hai gồm \(n\) số nguyên \(w_1, w_2, ..., w_n (1 \le w_i \le 10^6)\);
• Dòng thứ \(k (1 \le k \le n - 1)\) trong \(n - 1\) dòng tiếp theo chứa hai số \(u_k, v_k (1 \le u_k, v_k \le n)\)
  mô tả cạnh thứ \(k\) của cây.

Output

• Ghi ra thiết bị ra chuẩn một số nguyên là giá trị \(T\) tính được.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 700\);
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 7000\);
• Subtask \(3\) (\(20\%\) số điểm): \(1 \le w_i \le 2\);
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 10^5\);
• Subtask \(5\) (\(20\%\) số điểm): \(n \le 10^6\);

Example

4
1 1 2 3
1 2
1 3
1 4

8

4
1 2 2 2
1 2
2 3
3 4

3