trang chủ / đề bài / icpc25_nat_f

Bữa tiệc thịnh soạn

Đề bài

Mô tả

Sau cuộc đại di tản khỏi Tòa tháp của Thần, nhóm các thiếu nữ muốn ăn mừng bằng một bữa tiệc thật lớn. Và người phụ trách bữa tiệc không ai khác chính là thủ lĩnh tự phong của nhóm: Anh hùng Hameln!

Trong lúc vội vã, Hameln đã tìm được n loại gia vị và lần lượt đặt chúng lên một băng chuyền dẫn thẳng vào nồi. Gia vị thứ i có độ ngon là ai. Mải tự hào về tài nghệ khéo léo của mình, đến giây cuối cùng Hameln mới nhận ra một điều: một số gia vị có thể làm hỏng bữa tiệc! Nói cách khác, ai có thể âm.

Chỉ còn đúng một giây, Hameln nghĩ ra một kế hoạch tuyệt vời để cứu buổi ăn mừng:

  • Đầu tiên, cô chọn hai số l và r (1≤l≤r≤n) và đảo ngược đoạn băng chuyền chứa các gia vị al,al+1,…,ar.
  • Sau đó, cô chọn một số k (0≤k≤n). Cô chỉ dùng k gia vị đầu tiên và bỏ đi phần còn lại. Độ ngon của bữa tiệc là tổng độ ngon của k gia vị được dùng. Lưu ý rằng nếu Hameln dùng 0 gia vị thì độ ngon bằng 0.

Kế hoạch gần như ngọt ngào như bánh của Gretel, nhưng đầu óc của Hameln không sinh ra để đưa ra những quyết định này! Bạn hãy giúp cô tìm độ ngon lớn nhất của bữa tiệc nếu cô thực hiện kế hoạch một cách tối ưu.

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 t (1≤t≤104). Tiếp theo là mô tả các bộ dữ liệu.

  • Dòng đầu tiên chứa số nguyên n (2≤n≤2·105): số gia vị trên băng chuyền.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an (−109≤ai≤109).

Đảm bảo tổng n trên tất cả các bộ dữ liệu không vượt quá 2·105.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số: độ ngon lớn nhất mà Hameln có thể đạt được cho bữa tiệc.

Ràng buộc

  • 1≤t≤104.
  • 2≤n≤2·105, tổng n không vượt quá 2·105.
  • −109≤ai≤109.

Ví dụ

Input Output Giải thích
3
5
1 3 5 -7 9
4
-7 -1 -4 -6
10
1 -3 5 -7 9 -11 13 -15 17 -19
18
0
24
Bộ 1: đảo đoạn [−7,9], băng chuyền thành [1,3,5,9,−7], lấy 4 gia vị đầu: 1+3+5+9=18. Có thể chứng minh 18 là tốt nhất. Bộ 2: mọi gia vị đều âm nên bỏ hết, độ ngon bằng 0.
3
3
4 5 6
5
2 -5 3 -1 4
2
-3 8
15
8
8
Ví dụ bổ sung (không có trong đề gốc). Bộ 1: chọn l=r (không đổi gì) và lấy cả 3 gia vị. Bộ 2: đảo đoạn [−5,3,−1,4] thành [2,4,−1,3,−5], lấy 4 gia vị đầu. Bộ 3: đảo cả dãy thành [8,−3], lấy 1 gia vị.

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