trang chủ / đề bài / icpc23_mt_a

Đất nước Alpha

Đề bài

Mô tả

Ở đất nước Alpha có n hòn đảo được đánh số từ 1 đến n. Các hòn đảo được nối với nhau bằng những cây cầu một chiều: từ đảo i chỉ có thể đi sang đảo i+1. Mỗi khi đến một hòn đảo i, bạn sẽ được thưởng hoặc bị phạt mi đô la: mi dương là số tiền bạn nhận được, mi âm nghĩa là bạn phải nộp phạt |mi| đô la (số tiền hiện có của bạn được phép âm).

Một nhà ảo thuật cho Tuấn hai lần sử dụng phép thuật: một lần để dịch chuyển tới một hòn đảo bất kỳ (dùng lần đầu tiên để đến đất nước Alpha), sau đó Tuấn đi lần lượt sang các đảo kế tiếp, và một lần để trở về nhà vào bất kỳ lúc nào. Tuy nhiên, Tuấn phải gửi lại cho nhà ảo thuật một số tiền bằng số tiền lớn nhất mà anh nhận được ở một hòn đảo đã đi qua.

Nói cách khác, Tuấn chọn hai chỉ số l≤r, đi qua các đảo l,l+1,…,r và số tiền kiếm được là

(ml+ml+1+…+mr)−max(ml,ml+1,…,mr).

Tuấn sử dụng phép thuật một cách tối ưu để kiếm được nhiều tiền nhất. Hãy in ra số tiền lớn nhất mà Tuấn có thể kiếm được.

Dữ liệu vào

  • Dòng đầu tiên chứa một số nguyên n (1≤n≤105): số hòn đảo ở đất nước Alpha.
  • Dòng thứ hai chứa n số nguyên m1,m2,…,mn (−500≤mi≤500): số tiền được thưởng hoặc bị phạt ở đảo i.

Dữ liệu ra

In ra một số nguyên duy nhất là số tiền lớn nhất mà Tuấn có thể kiếm được.

Ràng buộc

  • 1≤n≤105
  • −500≤mi≤500

Ví dụ

Input Output Giải thích
5
6 -5 7 3 -2
4 Tuấn dịch chuyển tới đảo 1, đi qua các đảo 2,3,4 rồi về nhà ở đảo 4. Anh nhận được 6−5+7+3=11 đô la và gửi lại nhà ảo thuật 7 đô la, nên kiếm được 4 đô la.
8
-1 5 -4 3 4 6 -10 4
8 Tuấn dịch chuyển tới đảo 2 và về nhà ở đảo 6: nhận 5−4+3+4+6=14 đô la, gửi lại 6 đô la, kiếm được 8 đô la.

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