Chia nhóm
Xem PDF
Điểm:
600
Thời gian:
1.5s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho hai dãy \(a\) và \(b\) gồm \(N\) số nguyên, các phần tử của \(b\) đôi một khác nhau. Ta tìm cách chia nhóm các phần tử của \(a\), mỗi nhóm có ít nhất \(2\) phần tử. Trong mỗi nhóm, số điểm đạt được là phần tử \(a_i\) sở hữu \(b_i\) cao thứ hai trong nhóm. Hãy tìm cách chia dãy \(a\) thành các nhóm liên tiếp sao cho đạt được tổng số điểm của các nhóm là cao nhất.
Input
- Dòng đầu tiên chứa số nguyên dương \(N\) \((2\le n\le 3 * 10^5)\) thể hiện số phần tử trong hai dãy \(a\) và \(b\)
- Dòng thứ hai chứa n số nguyên \(a_1, a_2, a_3, ..., a_n\). \((|a_i|\le 10^9)\)
- Dòng thứ hai chứa n số nguyên \(b_1, b_2, b_3, ..., b_n\). \((|b_i|\le 10^9)\)
Output
- Một số nguyên duy nhất là kết quả của bài toán.
Scoring
- Subtask \(1\) (\(40\%\) số điểm): \(N\le 1000\)
- Subtask \(2\) (\(60\%\) số điểm): không có điều kiện gì thêm
Example
Test 1
Input
5
1 2 3 5 4
1 5 3 2 4Output
8Note
Ở test ví dụ \(1\), ta chia các phần tử thành \(2\) nhóm. Nhóm \(1\) gồm các phần tử \([1, 2, 3]\) và nhóm 2 gồm \([5, 4]\). Khi đó số điểm đạt được là \(3 + 5 = 8\).
Test 2
Input
5
-3 4 -10 2 7
1 4 3 2 5Output
4Note
Ở test ví dụ \(2\), phương án tối ưu nhất là chỉ gồm \(1\) nhóm duy nhất. Khi đó số điểm đạt được là \(4\)
Bình luận
em code O(n^2) vẫn ac ạ
phần tử a[i] sở hữu b[i] cao thứ 2 trong nhóm là sao
mổ test ví dụ đi
Ở test 2.
Chia nhóm thành -3 4 -10 2 7
Max là 7.
Số lớn nhì là 4 sao là kq=4 vậy