trang chủ / đề bài / icpc23_mt_j

Dải ô thứ nhất

Đề bài

Mô tả

Để chinh phục trái tim Yến Nhi, Quang Trí nhận một thử thách hóc búa từ cô. Yến Nhi vẽ trên sàn một dải gồm n ô vuông liên tiếp (gọi là dải thứ nhất), các ô được đánh số từ 1 tới n từ trái sang phải. Với mỗi ô, Quang Trí phải chọn tô màu đỏ hoặc màu xanh. Mọi ô đều phải được tô màu, tức là Quang Trí không được để trống ô nào.

Yến Nhi có n cây bút mực đỏ và n cây bút mực xanh để hỗ trợ Quang Trí tô màu. Mỗi cây bút chứa vừa đủ mực để tô đúng một ô với màu tương ứng.

Ban đầu Quang Trí có 0 điểm. Nếu muốn lấy i cây bút mực đỏ, Quang Trí bị trừ ai điểm. Tương tự, nếu muốn lấy j cây bút mực xanh, Quang Trí bị trừ bj điểm. Quy ước a0=b0=0.

Ngoài ra, Yến Nhi đưa ra một luật đặc biệt để Quang Trí được cộng điểm. Cô có một dải ô khác độ dài m (gọi là dải thứ hai) mà mọi ô đã được tô đỏ hoặc xanh. Với mỗi đoạn liên tiếp độ dài m của dải thứ nhất có cách tô trùng với dải thứ hai, Quang Trí được cộng D điểm. Cách tô của một đoạn được coi là trùng với cách tô của đoạn kia nếu không tồn tại cặp ô ở cùng vị trí (tính từ trái sang) trong hai đoạn mà có màu khác nhau. Các đoạn được tính có thể chồng lên nhau.

Quang Trí muốn tìm cách tô dải thứ nhất để điểm cuối cùng là lớn nhất (để gây ấn tượng tốt với Yến Nhi). Hãy giúp Quang Trí tìm cách tô tối ưu!

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên n, m, D (1≤n≤2000, 1≤m≤min(n,10), 1≤D≤106): độ dài dải thứ nhất, độ dài dải thứ hai và số điểm thưởng cho mỗi đoạn liên tiếp của dải thứ nhất có cách tô trùng với dải thứ hai.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an (1≤ai≤109).
  • Dòng thứ ba chứa n số nguyên b1,b2,…,bn (1≤bi≤109).
  • Dòng thứ tư chứa một xâu độ dài m gồm các ký tự 'R' hoặc 'B': ô tương ứng của dải thứ hai được tô màu đỏ hoặc xanh.

Dữ liệu ra

In ra hai dòng. Dòng đầu tiên là điểm cuối cùng lớn nhất mà Quang Trí đạt được. Dòng thứ hai là một xâu độ dài n mô tả cách tô: ký tự thứ i là 'R' nếu ô thứ i của dải thứ nhất được tô đỏ, ngược lại là 'B'. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

  • 1≤n≤2000, 1≤m≤min(n,10)
  • 1≤D≤106
  • 1≤ai,bi≤109

Ví dụ

Input Output Giải thích
6 2 1
1 2 3 4 5 6
6 5 4 3 2 1
RR
-1
RRRRRR
Có hai cách đạt −1 điểm. Dùng 6 bút đỏ: có 5 đoạn liên tiếp trùng với dải thứ hai, điểm là −a6−0+5·D=−6+5=−1. Dùng 6 bút xanh: không có đoạn nào trùng, điểm là −0−b6+0·D=−1.
6 2 4
1 2 3 4 5 6
6 5 5 3 2 1
RB
4
RBRBRB
Dùng 3 bút đỏ và 3 bút xanh, có 3 đoạn trùng: −a3−b3+3·4=−3−5+12=4.
6 2 3
1 2 6 4 5 6
6 5 4 3 2 1
RB
1
RBRBBB
Dùng 2 bút đỏ và 4 bút xanh, có 2 đoạn trùng: −a2−b4+2·3=−2−3+6=1.

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