CEOI 2018 - Day 1

Johnny thành lập Bytecomp, một công ty cung cấp năng lực tính toán trên đám mây. Những công ty như vậy thường có nhiều máy tính mạnh để chạy các tác vụ của khách hàng.

Hiện Johnny chưa mua máy nào. Cửa hàng cung cấp \(n\) máy tính. Mỗi máy có \(c_i\) lõi xử lý, tốc độ xung nhịp \(f_i\) và giá \(v_i\). Các lõi của cùng một máy hoạt động độc lập nên có thể được phân cho các tác vụ khác nhau.

Mỗi đơn đặt hàng của khách hàng gồm số lõi cần dùng \(C_j\), tốc độ xung nhịp tối thiểu \(F_j\) và khoản tiền khách hàng trả \(V_j\). Nếu nhận đơn, Johnny phải cung cấp đúng \(C_j\) lõi, có thể lấy từ nhiều máy khác nhau; mỗi lõi được cấp phải có tốc độ xung nhịp ít nhất \(F_j\) và không được cấp cho đơn hàng nào khác.

Hãy chọn các máy cần mua và các đơn hàng cần nhận sao cho mọi đơn được đáp ứng. Tối đa hóa lợi nhuận, bằng tổng tiền thu được từ các đơn hàng trừ tổng giá mua máy.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\) (\(1\le n\le2000\)), là số máy có thể mua.

Mỗi dòng trong \(n\) dòng tiếp theo chứa ba số nguyên \(c_i,f_i,v_i\) (\(1\le c_i\le50\), \(1\le f_i\le10^9\), \(1\le v_i\le10^9\)), lần lượt là số lõi, tốc độ xung nhịp và giá của máy thứ \(i\).

Dòng tiếp theo chứa số nguyên \(m\) (\(1\le m\le2000\)), là số đơn hàng.

Mỗi dòng trong \(m\) dòng tiếp theo chứa ba số nguyên \(C_j,F_j,V_j\) (\(1\le C_j\le50\), \(1\le F_j\le10^9\), \(1\le V_j\le10^9\)), lần lượt là số lõi cần dùng, tốc độ xung nhịp tối thiểu và khoản tiền của đơn hàng thứ \(j\).

Dữ liệu ra

In một số nguyên duy nhất là lợi nhuận lớn nhất có thể đạt được.

Ví dụ

4
4 2200 700
2 1800 10
20 2550 9999
4 2000 750
3
1 1500 300
6 1900 1500
3 2400 4550

350

Giải thích

Có thể mua hai máy lần lượt giá \(700\) và \(750\), thu tổng cộng \(1800\) từ hai đơn hàng đầu. Bốn lõi của máy thứ nhất có tốc độ \(2200\), bốn lõi của máy thứ hai có tốc độ \(2000\). Có thể cấp sáu lõi cho đơn thứ hai và một lõi cho đơn thứ nhất; một lõi còn lại không cần sử dụng. Lợi nhuận là \(1800-1450=350\).

Phân nhóm

1. \(18\) điểm: \(n\le15\).
2. \(18\) điểm: \(m\le15\).
3. \(18\) điểm: \(n,m\le250\) và \(c_i=C_j=1\) với mọi máy, đơn hàng.
4. \(18\) điểm: \(f_i=F_j=1\) với mọi máy, đơn hàng.
5. \(18\) điểm: \(v_i=V_j=1\) với mọi máy, đơn hàng.
6. \(10\) điểm: Không có ràng buộc bổ sung.

Biến đổi khí hậu là vấn đề quan trọng và Johnny hiểu điều đó. Anh muốn phân tích dữ liệu nhiệt độ lịch sử để tìm một dãy con tăng thật dài, qua đó thuyết phục những người chưa tin.

Dữ liệu gồm nhiệt độ \(t_i\) trong \(n\) ngày liên tiếp. Dãy con tăng là dãy các phần tử có chỉ số tăng nghiêm ngặt và giá trị cũng tăng nghiêm ngặt.

Để làm dãy con dài hơn, Johnny được chọn một đoạn ngày không rỗng và một số nguyên \(d\) (\(-x\le d\le x\)), rồi cộng \(d\) vào nhiệt độ của tất cả các ngày trong đoạn đó. Có thể chọn \(d=0\).

Hãy tìm độ dài lớn nhất của dãy con tăng dài nhất có thể đạt được sau thao tác.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,x\) (\(1\le n\le200000\), \(0\le x\le10^9\)), lần lượt là số ngày và giới hạn trị tuyệt đối của mức thay đổi.

Dòng thứ hai chứa \(n\) số nguyên \(t_1,t_2,\ldots,t_n\) (\(1\le t_i\le10^9\)), là nhiệt độ của các ngày.

Dữ liệu ra

In độ dài lớn nhất có thể của dãy con tăng.

Ví dụ

8 10
7 3 5 12 2 7 3 4

5

Giải thích

Có thể chọn đoạn ngày \([2,3]\) và \(d=-5\). Dãy nhiệt độ khi đó là \((7,-2,0,12,2,7,3,4)\); một dãy con tăng dài nhất là \((-2,0,2,3,4)\), có độ dài \(5\).

Phân nhóm

1. \(5\) điểm: \(n,x\le10\).
2. \(10\) điểm: \(n,x\le50\).
3. \(13\) điểm: \(n\le1000\).
4. \(10\) điểm: \(x=0\).
5. \(20\) điểm: \(x\le5\) và \(n\le50000\).
6. \(17\) điểm: \(x=10^9\).
7. \(25\) điểm: Không có ràng buộc bổ sung.

Bạn đã yêu thích trò xổ số Bytelotto từ lâu, nhưng gia đình luôn cho rằng chơi xổ số chỉ lãng phí tiền bạc. Bạn tin rằng họ nói vậy vì chưa biết cách chơi giỏi, và muốn chứng minh điều đó bằng toán học. Trong các trò xổ số, bạn chọn Bitlotto vì đây là trò đơn giản nhất: mỗi ngày có đúng một số được rút.

Bạn đã ghi lại kết quả quay số trong \(n\) ngày liên tiếp, tạo thành dãy \(a_1,a_2,\ldots,a_n\). Xét tất cả các đoạn liên tiếp có độ dài \(l\). Đoạn thứ \(i\) gồm các phần tử \(a_i,a_{i+1},\ldots,a_{i+l-1}\).

Khoảng cách giữa hai đoạn là số vị trí mà các phần tử tương ứng khác nhau. Hai đoạn được gọi là \(k\)-tương tự nếu khoảng cách giữa chúng không vượt quá \(k\).

Bạn cần trả lời \(q\) truy vấn. Với mỗi truy vấn cho một giá trị \(k_j\), hãy xác định với từng đoạn có bao nhiêu đoạn khác cùng độ dài là \(k_j\)-tương tự với nó. Không tính chính đoạn đó.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,l\) (\(1\le l\le n\le10000\)), lần lượt là số ngày và độ dài mỗi đoạn.

Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\) (\(1\le a_i\le10^9\)).

Dòng thứ ba chứa số nguyên \(q\) (\(1\le q\le100\)), là số truy vấn.

Mỗi dòng trong \(q\) dòng tiếp theo chứa số nguyên \(k_j\) (\(0\le k_j\le l\)).

Dữ liệu ra

Với mỗi truy vấn, in một dòng gồm \(n-l+1\) số nguyên. Số thứ \(i\) là số đoạn khác \(k_j\)-tương tự với đoạn thứ \(i\).

Ví dụ

6 2
1 2 1 3 2 1
2
1
2

2 1 1 1 1
4 4 4 4 4

Giải thích

Có năm đoạn độ dài \(2\): \((1,2)\), \((2,1)\), \((1,3)\), \((3,2)\) và \((2,1)\). Với \(k=1\), hai đoạn đầu tiên và đoạn thứ ba khác nhau đúng một vị trí; đoạn thứ nhất và đoạn thứ tư cũng vậy. Do đó, đoạn thứ nhất có hai đoạn khác \(1\)-tương tự. Với \(k=2\), mọi cặp đoạn đều \(2\)-tương tự.

Phân nhóm

1. \(25\) điểm: \(n\le300\).
2. \(20\) điểm: \(n\le2000\).
3. \(20\) điểm: \(q=1\) và \(k_1=0\).
4. \(15\) điểm: \(q=1\).
5. \(20\) điểm: Không có ràng buộc bổ sung.