Đề xuất 10 chuyên

Đề xuất 10 chuyên
Phân công 2 người (SCHE2N)
Có 2N việc đánh số 1, 2, ..., 2N cần được phân công cho hai người, mỗi người N việc. Thời gian làm việc i của người thứ nhất và người thứ hai tương ứng là ai, bi.
Hãy xác định tổng thời gian hoàn thành toàn bộ 2N việc nhỏ nhất có thể.
Dữ liệu
Dòng 1: số nguyên dương N (N≤4×105)
Dòng 2...2N+1: dòng i+1 ghi hai số nguyên dương a_i, biai, bi≤100
Kết quả
Dòng 1: số nguyên là tổng thời gian hai người làm hết 2N việc nhỏ nhất có thể.
Ví dụ
sche2n.inp
sche2n.out
2
2 1
3 2
5 3
1 2
8
Đo độ lớn (VALMETRIC)
Cho dãy số nguyên a1,a2,,aN. Ta định nghĩa độ lớn của mỗi phần tử ai 1≤i≤N là số lượng phần tử trong dãy nhỏ hơn ai.
Hãy xác định đoạn K phần tử liên tiếp của dãy có tổng độ lớn là lớn nhất.
Dữ liệu
Dòng 1: hai số nguyên N, K 1≤K≤N≤105
Dòng 2: N số nguyên a1,a2,,aN 1≤ai≤109 ∀i
Kết quả
Dòng 1: số nguyên là chỉ số phần tử bắt đầu của đoạn tìm được, nếu có nhiều nghiệm thì chọn đoạn trái nhất.
Ví dụ
valmetric.inp
valmetric.out
4 2
1 2 2 1
2
Hình chữ nhật con (SRECMAXP)
Cho lưới ô vuông kích thước M×N, các hàng đánh số 1M từ trên xuống, các cột đánh số 1N từ trái sang, ô (i,j) chứa kí tự ‘.’ hoặc ‘X’ thể hiện ô là trống hay có vật cản.
Hãy xác định chu vi lớn nhất có thể của một hình chữ nhật con cạnh song song với cạnh lưới gồm toàn các ô trống.
Dữ liệu
Dòng 1: hai số nguyên M, N (1≤M,N≤400)
Dòng 2M+1: dòng i+1 ghi xâu độ dài N thể hiện hàng i của lưới.
Kết quả
Dòng 1: số nguyên là chu vi lớn nhất có thể.
Ví dụ
srecmaxp.inp
srecmaxp.out
4 4
X.XX
X..X
..X.
..XX
10