Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
GSS - Đoạn con có tổng lớn nhất |
Cho dãy số a[1], a[2], ..., a[n] (|a[i]| <= 15000, n <= 50000).
Hàm q(x, y) = max { tổng(a[i]+a[i+1]+...+a[j]), x <= i <= j <= y }.
Cho m câu hỏi dạng x, y (1 <= x <= y <= n). (m <= 50000) -> hãy tính các q(x, y).
Input
- Dòng đầu là n.
- Dòng thứ hai là dãy a.
- Dòng thứ 3 là m.
- m dòng tiếp theo mỗi dòng là 1 cặp số x, y.
Output
-> Lần lượt ghi ra các q(x, y) tương ứng. Mỗi kết quả ghi trên 1 dòng.
Example
Input:
3
-1 2 3
1
1 2
Output:
2
Được gửi lên bởi: | Nguyen Dinh Tu |
Ngày: | 2006-10-24 |
Thời gian chạy: | 0.100s |
Giới hạn mã nguồn: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Ngôn ngữ cho phép: | Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET |
Nguồn bài: | Bai` nay Hieu add day nhe ^^ |
hide comments
|
|||||||
2011-07-11 15:26:26 Nguyễn Phúc Bình Nguyên
IT ra không nhỉ :-w |
|||||||
2010-11-28 09:50:33 TungNH
RMQ |