trang chủ / đề bài / icpc26_nat_m

Mì chính

Đề bài

Mô tả

MSG, tức mì chính (monosodium glutamate), ở Việt Nam còn được gọi là bột ngọt hay vị tinh, là một chất điều vị rất phổ biến trong ẩm thực Việt. MSG nổi tiếng với khả năng tạo vị umami cho các món canh, nước dùng và món xào. Nói ngắn gọn, theo lời một ông chú người Malaysia nọ, MSG là viết tắt của "Make Sh't Good". Fuiyoh!

Minh vừa mở một nhà hàng. Thực đơn của Minh gồm n món ăn, món thứ i thuộc loại ci. Một hôm, một ông chú người Malaysia ghé nhà hàng. Sau khi nếm cả n món của Minh, ông lắc đầu và thốt lên: "Đồ ăn của cậu có vị như nỗi buồn. MSG đâu? MSG là vua của hương vị. Thảo nào nhà hàng của cậu trống trơn như cuộc hôn nhân của tôi. Haiyaaa…". Minh lập tức nhận ra ông chú này là cao thủ thật sự, và quyết định nghe theo lời khuyên, thêm MSG vào các món ăn.

Sau khi phân tích kỹ, Minh xác định được rằng thêm MSG vào món thứ i sẽ làm độ ngon của món đó tăng thêm ai (ai có thể âm: trái với suy nghĩ của ông chú, MSG không làm mọi thứ ngon lên). Hơn nữa, thêm MSG vào nhiều món cùng một loại thì chỉ có tác dụng với món cuối cùng của loại đó. Nói cách khác, nếu Minh thêm MSG vào các món i1<i2<⋯<ik cùng một loại, thì chỉ món ik được tăng độ ngon thêm aik, còn độ ngon của các món i1,i2,…,ik−1 giữ nguyên.

Vì quá bận để tìm cách thêm MSG tối ưu, Minh quyết định chọn một đoạn khác rỗng [l,r] của thực đơn và thêm MSG vào tất cả các món l,l+1,…,r. Minh muốn biết tổng độ ngon tăng thêm lớn nhất có thể đạt được trong mọi đoạn [l,r]. Hãy giúp Minh tìm đáp án.

Dữ liệu vào

Mỗi file dữ liệu 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 đầu tiên của mỗi bộ dữ liệu chứa số nguyên n (1≤n≤106): số món trong thực đơn của Minh.
  • Dòng thứ hai chứa n số nguyên c1,c2,…,cn (1≤ci≤n): loại của các món ăn.
  • Dòng thứ ba chứa n số nguyên a1,a2,…,an (−109≤ai≤109): độ ngon tăng thêm của các món ăn.

Dữ liệu đảm bảo tổng n qua tất cả các bộ dữ liệu không vượt quá 106.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất: tổng độ ngon tăng thêm lớn nhất.

Ràng buộc

  • 1≤τ≤104.
  • 1≤n≤106; 1≤ci≤n; −109≤ai≤109.
  • Tổng n qua tất cả các bộ dữ liệu không vượt quá 106.

Ví dụ

Input Output Giải thích
4
3
1 1 2
1 -2 3
4
1 2 3 4
5 6 -7 8
2
1 1
-6 -7
5
1 3 2 3 4
100 -1000000000 1 -100 100
3
12
-6
101
Bộ thứ nhất: đoạn tối ưu là [3,3] với tổng 3. Với đoạn [1,3], món 1 và món 2 cùng loại 1 nên chỉ món 2 có tác dụng, tổng chỉ là −2+3=1. Bộ thứ hai: các món đôi một khác loại nên tổng của một đoạn chính là al+al+1+⋯+ar; đoạn tối ưu là [1,4] với tổng 5+6+(−7)+8=12. Bộ thứ ba: mọi đoạn đều có tổng âm; vì đoạn phải khác rỗng nên đoạn tối ưu là [1,1] với tổng −6. Bộ thứ tư: đoạn tối ưu là [1,5]; món 2 và món 4 cùng loại 3 nên chỉ món 4 có tác dụng và mức giảm rất lớn của món 2 bị bỏ qua, tổng là 100+1+(−100)+100=101.
2
4
1 2 3 2
5 -9 6 -1
3
1 1 1
3 -1 2
10
3
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: đoạn [1,4] có món 2 bị món 4 cùng loại thay thế, tổng là 5+6+(−1)=10, lớn hơn mọi đoạn khác (ví dụ [1,3] chỉ được 5+(−9)+6=2). Bộ thứ hai: mọi món cùng một loại nên tổng của đoạn [l,r] luôn là ar; đáp án là a1=3.

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