# Câu 2: Đầu bếp

### Tóm tắt bài toán :
Cho $n$ dĩa bánh lọc, $a_i$ và $b_i$ tương ứng là độ ngon của dĩa bánh bèo và bánh lọc của người thứ $i$. Yêu cầu với mỗi số nguyên $k$ $(1 ≤ k ≤ n)$, tính tổng độ ngon lớn nhất có thể khi nhóm khách hàng chọn $k$ dĩa bánh bèo và $n - k$ dĩa bánh lọc .

### Subtask 1, 2: Dãy $a$ được sắp xếp không giảm, dãy $b$ được sắp xếp không tăng
- Duyệt for $i$ từ $1 \rightarrow n$, in ra tổng của $a[n -i + 1 .. n] + b[1 .. n - i]$ của $i$ phần tử đầu tiên .
- Độ phức tạp: $O(n)$

### Subtask 3: $n ≤ 20$
- Sử dụng quay lui để in ra mọi trường hợp thõa mãn điều kiện lấy $i$ dĩa bánh bèo và $n - i$ dĩa bánh lọc và in ra trường hợp lớn nhất .
- Độ phức tạp: $O(2 ^ n)$

### Subtask 4: Không ràng buộc gì thêm

- Mặc định $sum$ là tổng của $n$ dĩa bánh lọc và dùng mảng ans lưu lại chênh lệch giữa $a_i$ và $b_i$ theo thứ tự giảm dần . Kết quả chỉ cần for $i$ từ $1 \rightarrow n$, $ans[1 ..i]$ $+$ $sum$ . (có thể dùng hàng đợi ưu tiên)

#

**Code Tham Khảo** : [**here**](https://ideone.com/6d5irc)