Bedao Regular Contest 16 - MAXPROD

View as PDF

Submit solution


Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

Please read the guidelines before commenting.



  • 1
    Thangdeptrai  commented on Aug. 21, 2023, 3:54 p.m.

    sao từ test 14 đến 51 AC mà mấy test trc lại sai nhỉ :vvv


    • 1
      Thangdeptrai  commented on Aug. 21, 2023, 3:56 p.m.

      code: https://ideone.com/03ZhC0


      • 6
        duybinh_cbl  commented on Aug. 22, 2023, 1:25 p.m.

        cũng bị ngộ nhận như v lúc làm contest =)), đổi thành thử từng vị trí đi.


        • 2
          Thangdeptrai  commented on Aug. 23, 2023, 1:47 p.m.

          Cảm ơn bạn nha


  • 2
    trinhtung2007  commented on Aug. 19, 2023, 3:12 p.m.

    ai có thể giải thích thêm về cái thuật full đc ko :vv