Square Pairs

Nộp bài
Time limit: 1.0 / Memory limit: 512M

Point: 100

Cho hai số nguyên dương ~n~ và ~m~, hãy đếm số lượng cặp số nguyên ~(a,b)~ thỏa mãn điều kiện sau:

  • ~a\times b \leq m~
  • ~1\leq a < b \leq n~
  • ~a\times b~ là số chính phương

Input

  • Dòng đầu chứa số nguyên dương ~n~ (~1 \le n \le 10^{7}~).
  • Dòng thứ hai chứa số nguyên dương ~m~ (~1 \le m \le 10^{14}~).

Output

  • Một số nguyên duy nhất là số lượng cặp số thỏa mãn.

Sample Input

4
4

Sample Output

1

Subtask

  • ~20\%~ số test có ~n \le 3\,000~
  • ~20\%~ số test tiếp theo có ~n \le 10^5, m \le 10^6~
  • ~30\%~ số test tiếp theo có ~n \le 10^6~
  • ~30\%~ số test còn lại không có điều kiện gì thêm

Giải thích

Cặp số duy nhất thỏa mãn là ~a=1,b=4~


Watermelon

Nộp bài
Time limit: 1.0 / Memory limit: 1G

Point: 100

It's not a bug — it's an undocumented feature 😈

Cho một dãy số nguyên ~A~ gồm ~n~ phần tử, được đánh số ~A_1,A_2,...,A_n~.

Ta có một số định nghĩa như sau:

  • Trọng số của đoạn con (ở đây là một đoạn con liên tiếp) là tổng các giá trị ~A_i~ trong đoạn.
  • Độ cân bằng của dãy ~A~ là trọng số của đoạn con có trọng số lớn nhất trong dãy số.

Bài toán sẽ thật dễ dàng nếu chỉ yêu cầu tính độ cân bằng của dãy ~A~ được cho, vậy nên ~Watermelon~ - người thầy của muôn quả - đã quyết định tăng độ khó bằng cách sau:

  • Đầu tiên, thầy đưa ra một dãy số nguyên gồm ~n~ phần tử ~B_1,B_2,...,B_n~.
  • Có tối đa ~k~ lượt chỉnh sửa, mỗi lượt bạn được chọn một đoạn con các phần tử từ vị trí thứ ~l~ đến vị trí thứ ~r~ ~(1 \le l \le r \le n)~ và thực hiện phép gán ~A_i = A_i*B_i~ với ~\forall i \in [l,r]~.

Yêu cầu: Đưa ra được độ cân bằng lớn nhất với tối đa ~k~ lượt chỉnh sửa.

Hoa Quả Sơn đã phải bó cành trước bài toán mới này, bạn hãy giúp họ tìm kiếm câu trả lời.

Input: watermelon.inp

  • Dòng đầu tiên gồm hai số nguyên ~n~ và ~k~ ~(1 \le n \le 10^5, 0 \le k \le 10)~.
  • Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy số nguyên ~A_1, A_2, ..., A_n~ ~(|A_i| \le 1000)~.
  • Dòng thứ ba gồm ~n~ số nguyên dương miêu tả dãy số nguyên ~B_1, B_2, ..., B_n~ ~(|B_i| \le 10)~.

Output: watermelon.out

  • In ra một số nguyên duy nhất là độ cân bằng lớn nhất tìm được của dãy ~A~ sau khi sử dụng tối đa ~k~ lượt chỉnh sửa.

Scoring:

  • Subtask ~1~ ~(15\%)~: ~k = 0~.
  • Subtask ~2~ ~(15\%)~: ~k = 1~ và ~n \le 5000~.
  • Subtask ~3~ ~(20\%)~: ~k = 1~.
  • Subtask ~4~ ~(25\%)~: ~k = 2~.
  • Subtask ~5~ ~(25\%)~: Không ràng buộc gì thêm.

Sample Input 1

5 1
-3 4 -5 2 -2
1 -2 -1 2 1

Sample Output 1

13

Sample Input 2

3 0
-4 -10 -8
2 2 -1

Sample Output 2

-4

Explanation:

  • Trong ví dụ thứ nhất, cách tối ưu nhất là chọn đoạn ~[3, 4]~ để tác động. Như vậy dãy ~A~ mới là ~[-3, 4, 5, 4, -2]~. Vậy độ cân bằng của dãy này là ~13~.
  • Trong ví dụ thứ ~2~, khi ~k = 0~, bạn không thực hiện lượt chỉnh sửa nào và đưa ra độ cân bằng của dãy ~A~ ban đầu là ~-4~.

Dance Group

Nộp bài
Time limit: 1.5 / Memory limit: 1G

Point: 100

Một lớp học nhảy có ~n~ học viên nam và ~n~ học viên nữ. Cho ~m~ thông tin về các cặp học viên, thông tin thứ ~k~ ~(1 \le k \le m)~ cho biết học viên nam thứ ~i_k~ ~(1 \le i_k \le n)~ có thể nhảy cặp với học viên nữ thứ ~j_k~ ~(1 \le j_k \le n)~ .

Trong một buổi học, sau khi hướng dẫn cho tất cả các học viên, thầy giáo muốn chọn ra hai đôi nhảy, mỗi đôi gồm hai học viên (một nam và một nữ) để trình diễn và rút kinh nghiệm. Trong quá trình biểu diễn, hai cặp này sẽ đổi bạn nhảy cho nhau, do đó, thầy giáo muốn lựa chọn ra hai đôi nhảy mà khi đổi bạn nhảy, hai học viên ở đôi nhảy mới vẫn có thể nhảy cặp với nhau.

Yêu cầu: Cho ~m~ thông tin về các cặp học viên, hãy đếm số cách chọn hai cặp nhảy thỏa mãn. Hai cặp nhảy được gọi khác nhau nếu tồn tại một người thuộc vào hai cặp nhảy này nhưng không thuộc hai cặp nhảy kia.

Input
  • Dòng đầu chứa hai số nguyên dương ~ n,m~ ~(m \le n^2)~
  • Dòng thứ ~k~ ~(1 \le k \le m)~ trong ~m~ dòng tiếp theo chứa hai số nguyên ~i_k, j_k~ ~(1 \le i_k , j_k \le n)~ mô tả thông tin về cặp học viên thứ ~k~.
Output
  • Ghi ra thiết bị ra chuẩn một số nguyên là số cách chọn hai cặp nhảy thỏa mãn.
Subtask
  • ~20\%~ số test: ~n \le 50~
  • ~20\%~ số test khác : ~n \leq 300~.
  • ~20\%~ số test khác : ~n \leq 10^3, m \le 2 \times 10^4~.
  • ~20\%~ số test khác : ~n \leq 5 \times 10^3, m \le 2 \times 10^4~.
  • ~20\%~ số test còn lại : ~n,m \leq 10^5~.
Example
Input 1
3 7
1 1
1 2
2 1
2 2
2 3
3 2
3 3
Output 1
2
Explanation

Imgur


Time limit: 1.0 / Memory limit: 512M

Point: 100

Công ty của Alice vừa thiết kế một loại robot thông minh mới. Để đánh giá khả năng tự vận hành của robot, Alice tạo ra một bức tường từ ~n~ cột các khối lập phương. Các cột đặt cạnh nhau với bề dày bức tường là 1, và chiều cao tương ứng của các cột được mô tả bởi mảng ~a = {a_1, a_2, \ldots, a_n}~, trong đó ~a_i~ là độ cao cột thứ ~i~ (số khối lập phương).

Robot được giao nhiệm vụ thay đổi bức tường để có độ cao mới được mô tả bởi mảng ~b = {b_1, b_2, \ldots, b_n}~.

Robot chỉ có thể thực hiện ba loại thao tác sau đây:

  • Thao tác loại 1: Lấy khối trên cùng của một cột để bỏ đi. Thời gian thực hiện thao tác này là ~x~.
  • Thao tác loại 2: Lấy một khối mới và đặt lên trên cùng của một cột. Thời gian thực hiện thao tác này là ~y~.
  • Thao tác loại 3: Chuyển một khối từ cột ~i~ sang cột ~j~. Thời gian thực hiện thao tác này là ~z \times |i - j|~, trong đó ~|i - j|~ là khoảng cách giữa hai cột.

Yêu cầu: Cho ~a_1, a_2, . . . , a_n; b_1, b_2, . . . , b_n~ và ~x, y, z~. Hãy xác định thời gian ngắn nhất để robot hoàn thành nhiệm vụ.

Input
  • Dòng đầu chứa bốn số nguyên dương ~n~, ~x~, ~y~, ~z~ (~x, y, z \leq 1000~).
  • Dòng thứ hai gồm ~n~ số nguyên không âm ~a_1, a_2, \ldots, a_n~ (~a_i \leq 10~).
  • Dòng thứ ba gồm ~n~ số nguyên không âm ~b_1, b_2, \ldots, b_n~ (~b_i \leq 10~).
Output
  • Một số nguyên duy nhất là thời gian tối thiểu để robot hoàn thành nhiệm vụ.
Subtask
  • ~25\%~ số test: ~n \leq 10~ và ~a_i, b_i \leq 1~.

  • ~25\%~ số test khác : ~n \leq 10^2~ và ~a_i, b_i \leq 1~.

  • ~25\%~ số test khác : ~n \leq 10^3~.

  • ~25\%~ số test còn lại : ~n \leq 10^5~.

Example
Input 1
4 10 10 1
1 2 2 4
2 2 2 2
Output 1
13