VODIVIDE - VOI 2015 Day 2 - Chia phần
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Vinh và Sơn có N đồng tiền cổ, N là số chẵn. Ta tạm đánh số các đồng tiền cổ này theo thứ tự từ 1->N. Đồng tiền thứ i Vinh định giá nó là ai còn Sơn định giá nó là bi.
Vinh và Sơn tiền hành phân chia số tiền này, lần lượt thực hiện N/2 lượt . Ở lượt chơi thứ t, Sơn lấy ra 2 đồng tiền, Vinh sẽ lấy đồng tiền nào có giá trị lớn hơn trong 2 đồng tiền theo như Vinh định giá, và Sơn sẽ lấy đồng tiền còn lại.
Sơn biết tất cả các số ai, bi (i=1..N) và mỗi bước Sơn được quyền chọn cách lấy 2 đồng tiền tùy theo ý thích của mình.
Hãy giúp Sơn tiền hành việc phân chia các đồng tiền sao cho tổng giá trị các đồng tiền Sơn nhận được là lớn nhất có thể.
Input
- Dòng đầu tiên chứa số nguyên dương chẵn N là số đồng tiền.
- Dòng thứ 2 chứa N số nguyên dương a1, a2, ..., aN mỗi số ko vượt quá 400000
- Dòng thứ 3 chứa N số nguyên dương b1, b2, ..., bN mỗi số ko vượt quá 400000.
Output
Dòng đầu tiên ghi ra tổng số tiền lớn nhất mà Sơn nhận được.
N/2 dòng tiếp theo mỗi dòng ghi cặp 2 chỉ số các đồng tiền mà Sơn lấy ra theo đúng thứ tự mỗi lượt thực hiện chia phần. Nếu có nhiều phương án in ra 1 phương án bất kì.
Example
Input: 6 6 10 11 18 5 14 1 7 6 12 15 1 Output: 28 5 1 2 6 3 4
Giới hạn:
- 30% số test với N <= 5000 và ai = bi với i = 1..N;
- 30% số test với N <= 20
- 40% số test còn lại với N <= 5000
- Người up: voj
- Nguồn bài: VOI15 day 2