Bedao Regular Contest 16 - MAXPROD

Xem dạng PDF

Gửi bài giải


Điểm: 0,20 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
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

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 1
    Thangdeptrai  đã bình luận lúc 21, Tháng 8, 2023, 15:54

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


    • 1
      Thangdeptrai  đã bình luận lúc 21, Tháng 8, 2023, 15:56

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


      • 5
        duybinh_cbl  đã bình luận lúc 22, Tháng 8, 2023, 13:25

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


        • 3
          Thangdeptrai  đã bình luận lúc 23, Tháng 8, 2023, 13:47

          Cảm ơn bạn nha


  • 3
    trinhtung2007  đã bình luận lúc 19, Tháng 8, 2023, 15:12

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