Bedao Grand Contest 13 - MAXSEG
View as PDF
Cho dãy ~a~ gồm ~n~ phần tử nguyên và một hoán vị ~p~ độ dài ~n~.
Ta thực hiện một trò chơi gồm ~n~ bước như sau: ở bước thứ ~i~, ta xóa đi phần tử ~p_i~.
Yêu cầu: Trước khi thực hiện mỗi bước, hãy in ra tổng lớn nhất của đoạn con gồm các phần tử liên tiếp, có độ dài lớn hơn ~0~ và chưa có phần tử nào bị xóa trên dãy ~a~.
Input
Dòng đầu tiên chứa số nguyên dương ~n~ miêu tả độ dài dãy ~a~ và hoán vị ~p~ ~(1 \le n \le 5*10^5)~.
Dòng thứ hai gồm ~n~ số nguyên miêu tả dãy ~a_1,a_2,...,a_n~ ~( |a_i| \le 10^9)~
Dòng thứ ba gồm ~n~ số nguyên dương miêu tả dãy hoán vị ~p_1,p_2,...,p_n~
Output
- Gồm ~n~ dòng, dòng thứ ~i~ in ra giá trị của đoạn con gồm các phần tử liên tiếp chưa có phần tử nào bị xóa và có tổng lớn nhất trước bước thứ ~i~.
Scoring
Subtask ~1~ (~30~ điểm): ~n \le 5000~
Subtask ~2~ (~30~ điểm): ~a_i > 0~
Subtask ~3~ (~40~ điểm): Không ràng buộc gì thêm.
Sample Input 1
7
4 -1 2 -3 4 -2 3
6 1 5 2 7 4 3
Sample Output 1
7
6
4
3
3
2
2
Notes
Trước khi thực hiện thao tác ~1~, dãy là [~4~, ~-1~, ~2~, ~-3~, ~4~, ~-2~, ~3~], đoạn con lớn nhất thỏa mãn là ~[1,7]~
Trước khi thực hiện thao tác ~2~, dãy là [~4~, ~-1~, ~2~, ~-3~, ~4~, ~*~, ~3~], đoạn con lớn nhất thỏa mãn là ~[1,5]~
Trước khi thực hiện thao tác ~3~, dãy là [~*~, ~-1~, ~2~, ~-3~, ~4~, ~*~, ~3~], đoạn con lớn nhất thỏa mãn là ~[5,5]~
Trước khi thực hiện thao tác ~4~, dãy là [~*~, ~-1~, ~2~, ~-3~, ~*~, ~*~, ~3~], đoạn con lớn nhất thỏa mãn là ~[7,7]~
Trước khi thực hiện thao tác ~5~, dãy là [~*~, ~*~, ~2~, ~-3~, ~*~, ~*~, ~3~], đoạn con lớn nhất thỏa mãn là ~[7,7]~
Trước khi thực hiện thao tác ~6~, dãy là [~*~, ~*~, ~2~, ~-3~, ~*~, ~*~, ~*~], đoạn con lớn nhất thỏa mãn là ~[3,3]~
Trước khi thực hiện thao tác ~7~, dãy là [~*~, ~*~, ~2~, ~*~, ~*~, ~*~, ~*~], đoạn con lớn nhất thỏa mãn là ~[3,3]~
Comments
Nguồn: https://codeforces.com/contest/722/problem/C
cảm ơn bạn dù 2 bài nó không được giống nhau lắm :))))
This comment is hidden due to too much negative feedback. Show it anyway.