trang chủ / đề bài / icpc26_mt_a

Ngày chụp ảnh

Đề bài

Mô tả

Hôm nay là ngày chụp ảnh ở một trường tiểu học. n học sinh đứng thành một hàng dọc, trong đó n là số chẵn; học sinh thứ i tính từ đầu hàng có chiều cao hi và các chiều cao đôi một khác nhau.

Mỗi người trong hàng phải xuất hiện trong đúng một bức ảnh. Với một bức ảnh, thợ ảnh gọi 2k người bất kỳ vẫn còn trong hàng (k≥1), không nhất thiết đứng cạnh nhau. Theo thứ tự trong hàng, k người đầu tiên trong số họ tạo thành một hàng ảnh và k người còn lại tạo thành một hàng ảnh khác. Thợ ảnh chọn hàng ảnh nào đứng trước; hàng còn lại đứng ngay phía sau. Những người trong cùng một hàng ảnh có thể đứng theo thứ tự bất kỳ, vì vậy để chắc chắn không ai bị che khuất, người thấp nhất ở hàng sau phải cao hơn người cao nhất ở hàng trước.

Ví dụ, với hàng 135,142,158,150,128,118,124,110, nếu gọi sáu bạn 142,158,128,118,124,110 thì hàng ảnh thứ nhất là {142,158,128}, hàng ảnh thứ hai là {118,124,110}, và có thể chụp với hàng thứ hai đứng trước, vì người thấp nhất ở hàng sau (128) cao hơn người cao nhất ở hàng trước (124). Ngược lại, với hàng 135,118,124,150,110,142,158,128, nếu gọi bốn bạn 135,118,110,142 thì hai hàng ảnh {135,118} và {110,142} không thể tạo thành một bức ảnh: dù hàng nào đứng sau thì vẫn có thể có người bị che khuất.

Trước khi chụp ảnh, cô giáo có thể cho hai bạn đứng cạnh nhau trong hàng đổi chỗ cho nhau, bao nhiêu lần cũng được. Mỗi lần đổi chỗ mất a giây và mỗi bức ảnh mất b giây.

Yêu cầu: Tìm tổng thời gian nhỏ nhất để chụp ảnh cho tất cả mọi người.

Dữ liệu vào

  • Dòng đầu tiên gồm ba số nguyên n, a và b (2≤n≤2×105, n chẵn, 1≤a,b≤106): số học sinh, thời gian một lần đổi chỗ và thời gian chụp một bức ảnh, tính bằng giây.
  • Dòng thứ hai gồm n số nguyên đôi một khác nhau h1,h2,…,hn (1≤hi≤109): chiều cao của các học sinh từ đầu hàng đến cuối hàng.

Dữ liệu ra

In ra một số nguyên duy nhất: tổng thời gian nhỏ nhất, tính bằng giây.

Ràng buộc

  • 2≤n≤2×105, n chẵn.
  • 1≤a,b≤106.
  • 1≤hi≤109, các hi đôi một khác nhau.

Ví dụ

Input Output Giải thích
4 1 10
120 130 110 140
11 Hai bạn cao 130 và 110 đổi chỗ, hàng trở thành 120,110,130,140. Sau đó một bức ảnh chụp tất cả: 120,110 đứng trước, 130,140 đứng sau. Tổng thời gian là 1+10=11.
4 20 10
120 130 110 140
20 Không đổi chỗ, chụp hai bức ảnh: đầu tiên 120 đứng trước 140, sau đó 110 đứng trước 130. Tổng thời gian là 10+10=20.

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