trang chủ / đề bài / icpc25_reg_a

Âu thuyền

Đề bài

Mô tả

Âu thuyền là một buồng có cửa chắn, dùng trên kênh đào và sông để đưa thuyền qua lại giữa các đoạn nước có độ cao khác nhau. Khi thuyền đi vào buồng, các cửa được đóng lại, mực nước trong buồng được dâng lên hoặc hạ xuống cho bằng đoạn nước kế tiếp, và thuyền tiếp tục hành trình một cách êm ả. Nhờ có âu thuyền, những tuyến đường thủy dài có thể vượt đồi và băng qua nhiều dạng địa hình mà không cần một lộ trình hoàn toàn bằng phẳng.

Khi đưa thuyền lên dốc: (1) thuyền ở độ cao thấp, cửa trái mở để thuyền đi vào; (2) thuyền vào buồng, cả hai cửa đóng lại; (3) nước được bơm vào buồng, mực nước dâng lên; (4) thuyền đã ở độ cao cao hơn, cửa phải mở để thuyền đi ra; (5) thuyền rời buồng. Khi đưa thuyền xuống dốc thì làm tương tự: thuyền vào từ cửa phải ở độ cao cao, cả hai cửa đóng, nước được rút bớt khỏi buồng để hạ mực nước, rồi cửa trái mở cho thuyền đi ra ở độ cao thấp hơn.

Bạn phụ trách hệ thống âu thuyền phức tạp nhất thế giới, gồm n buồng. Buồng thứ i đặt ngay tại độ cao hi (0=h0<h1<h2<…<hn) và có thể đưa thuyền từ độ cao hi−1 lên độ cao hi và ngược lại. Buồng thứ i có diện tích đáy si, nghĩa là lượng nước cần để vận hành buồng thứ i là si·(hi−hi−1). Lượng nước cần để vận hành cả hệ thống được định nghĩa là lượng nước lớn nhất cần cho một buồng nào đó trong hệ thống.

Để cắt giảm chi phí vận hành, bạn được giao nhiệm vụ giảm số buồng xuống còn k. Để làm điều đó, bạn được thực hiện thao tác sau đúng n−k lần:

  • Giả sử số buồng hiện tại là n′. Chọn hai buồng liên tiếp i và i+1 (i≤n′−1). Chúng được thay bằng một buồng duy nhất:

    • nối thẳng độ cao hi−1 với độ cao hi+1 (độ cao hi biến mất khỏi hệ thống);
    • có diện tích đáy si+si+1.

    Sau khi gộp, số buồng giảm đi 1 và các buồng được đánh số lại từ 1 đến n′−1 theo thứ tự độ cao tăng dần.

Chi phí vận hành là quan trọng, nhưng tiết kiệm nước cũng quan trọng không kém. Trong tất cả các cách giảm số buồng xuống còn k, hãy tìm lượng nước nhỏ nhất có thể cần để vận hành cả hệ thống.

Dữ liệu vào

Mỗi test gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu τ (1≤τ≤104). Tiếp theo là mô tả các bộ dữ liệu:

  • Dòng thứ nhất chứa hai số nguyên n và k (1≤k<n≤2·105): số buồng ban đầu của hệ thống và số buồng cần đạt được.
  • Dòng thứ hai chứa n số nguyên h1,h2,…,hn (0<h1<h2<…<hn≤106): các độ cao đặt buồng.
  • Dòng thứ ba chứa n số nguyên s1,s2,…,sn (1≤si≤106): diện tích đáy của các buồng.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra lượng nước nhỏ nhất có thể cần để vận hành cả hệ thống, trong tất cả các cách giảm số buồng xuống còn k.

Ràng buộc

  • 1≤τ≤104.
  • 1≤k<n≤2·105.
  • 0<h1<h2<…<hn≤106.
  • 1≤si≤106.

Ví dụ

Input Output Giải thích
2
3 2
2 3 5
7 9 8
4 2
1 2 3 4
1 1 1 1
48
4
Bộ thứ nhất: có 2 cách. Gộp buồng 1 và 2: buồng mới nối độ cao 0 với 3, diện tích đáy 7+9=16, cần 16·3=48; buồng còn lại cần 8·(5−3)=16; cả hệ thống cần max{48,16}=48. Gộp buồng 2 và 3: buồng thứ nhất cần 14, buồng mới cần (5−2)·(9+8)=51, cả hệ thống cần 51. Đáp án là 48. Bộ thứ hai: gộp hai buồng đầu thành buồng cần 4, gộp hai buồng cuối thành buồng cần 4.
1
5 3
1 3 4 8 10
2 1 5 1 3
24 Ví dụ bổ sung (không có trong đề gốc). Gộp buồng 2 với 3, và buồng 4 với 5: các buồng cần 2·1=2, (4−1)·6=18 và (10−4)·4=24.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0