Bedao Regular Contest 16 - MAXPROD
View as PDF
Trung có hai dãy ~a~, ~b~ gồm ~n~ phần tử. Trung sẽ thực hiện thao tác sau ~k~ lần:
- Chọn một vị trí ~i~ bất kì, và tăng ~a_i~ hoặc ~b_i~ lên ~1~ đơn vị.
Trung muốn ~\sum \limits_{i = 1}^{n} a_i \cdot b_i~ đạt giá trị lớn nhất có thể, hay nói cách khác, tổng của tích các cặp số nằm ở vị trí ~i~ là lớn nhất có thể. Hãy thực hiện ~k~ thao tác một cách hợp lý để Trung đạt được mục tiêu ấy nhé!
Input
Dòng đầu tiên chứa số nguyên dương ~n~ và ~k~ (~1 \le n \le 10^5, 1 \le k \le 10^9~) — số phần tử của dãy ~a~, ~b~ và số thao tác được thực hiện.
Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^5~) — các phần tử của dãy ~a~.
Dòng tiếp theo chứa ~n~ số nguyên dương ~b_1, b_2, \ldots, b_n~ (~1 \le b_i \le 10^5~) — các phần tử của dãy ~b~.
Output
Một dòng duy nhất chứa đáp án của bài toán: giá trị lớn nhất có thể của ~\sum \limits_{i = 1}^{n} a_i \cdot b_i~ sau khi thực hiện ~k~ thao tác.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~24~ | ~n \le 3000~ |
| 2 | ~76~ | không có giới hạn gì thêm |
Sample Input 1
6 7
2 1 2 3 3 6
8 3 3 4 8 8
Sample Output 1
171
Comments
sao từ test 14 đến 51 AC mà mấy test trc lại sai nhỉ :vvv
code: https://ideone.com/03ZhC0
cũng bị ngộ nhận như v lúc làm contest =)), đổi thành thử từng vị trí đi.
Cảm ơn bạn nha
ai có thể giải thích thêm về cái thuật full đc ko :vv