JOI 2026 - Shopping 3

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 1800 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cửa hàng JOI có \(N\) mặt hàng, đánh số từ \(1\) đến \(N\); mặt hàng \(i\) có giá niêm yết \(A_i\). Khi mua hàng qua Internet, khách có thể sử dụng phiếu giảm giá. Có \(Q\) loại phiếu, đánh số từ \(1\) đến \(Q\). Với phiếu loại \(j\), nếu dùng \(k\) phiếu, với \(k\) là một số nguyên không âm, cùng áp dụng cho tất cả mặt hàng thì giá mỗi mặt hàng \(i\) trở thành \(\max(0,A_i-D_jk)\), đồng thời trả thêm một khoản phí chung \(C_jk\) cho cả lần mua hàng, không phải cho từng mặt hàng.

Trong mỗi truy vấn \(j\), chỉ được dùng phiếu loại \(j\) với số lượng tùy ý để mua mỗi mặt hàng một lần. Hãy tìm tổng tiền nhỏ nhất cho từng truy vấn.

Dữ liệu vào

Dòng đầu chứa \(N,Q\). Dòng thứ hai chứa \(A_1,\ldots,A_N\). \(Q\) dòng tiếp theo, dòng \(j\) chứa \(C_j,D_j\).

Dữ liệu ra

In \(Q\) dòng; dòng \(j\) là đáp án của truy vấn \(j\).

Ràng buộc

  • \(1 \le N,Q \le 300000\).
  • \(1 \le A_i,C_j,D_j \le 10^9\).
  • Mọi giá trị số trong dữ liệu vào đều là số nguyên.

Phân nhóm

  1. \(6\) điểm: \(N=1\), \(Q \le 3000\).
  2. \(3\) điểm: \(N,Q \le100\), \(A_i\le100\).
  3. \(8\) điểm: \(N,Q\le3000\), mọi \(D_j=1\).
  4. \(22\) điểm: \(N,Q\le3000\).
  5. \(15\) điểm: mọi \(D_j=1\).
  6. \(18\) điểm: mọi \(A_i\le1000000\).
  7. \(28\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input 
3 4
8 10 3
12 5
3 2
3 4
100 100
Output 
20
14
8
21
Giải thích

Với truy vấn \(1\), dùng một phiếu loại \(1\) làm giá các mặt hàng thành \(3,5,0\). Tổng tiền là \(3+5+0+12\times1=20\). Không thể trả ít hơn \(20\).

Với truy vấn \(2\), dùng bốn phiếu loại \(2\) làm giá các mặt hàng thành \(0,2,0\). Tổng tiền là \(0+2+0+3\times4=14\). Không thể trả ít hơn \(14\).

Với truy vấn \(3\), dùng hai phiếu loại \(3\) làm giá các mặt hàng thành \(0,2,0\). Tổng tiền là \(0+2+0+3\times2=8\). Không thể trả ít hơn \(8\).

Với truy vấn \(4\), không dùng phiếu nào, giá các mặt hàng là \(8,10,3\) và tổng tiền là \(8+10+3+100\times0=21\). Không thể trả ít hơn \(21\). Vì thế lần lượt in \(20,14,8,21\).

Ví dụ này thỏa mãn các nhóm \(2\), \(4\), \(6\), \(7\).

Ví dụ 2

Input 
1 3
83
2 5
4 5
6 5
Output 
34
67
83
Giải thích

Ví dụ này thỏa mãn các nhóm \(1\), \(2\), \(4\), \(6\), \(7\).

Ví dụ 3

Input 
15 3
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
1 1
10 1
20 1
Output 
9
67
77
Giải thích

Ví dụ này thỏa mãn các nhóm \(2\), \(3\), \(4\), \(5\), \(6\), \(7\).

Ví dụ 4

Input 
6 3
1000000000 999999999 999999998 999999997 999999996 999999995
1000000000 1
1 1000000000
900000000 900000000
Output 
5999999985
1
1499999985
Giải thích

Ví dụ này thỏa mãn các nhóm \(4\), \(7\).

Nguồn

JOI 2025/2026 - Vòng loại 2, bài Shopping 3.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.

Tệp

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: