Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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
2019-10-28 15:46:46


Last edit: 2019-10-28 16:08:58
2019-06-30 06:26:04
1 đấm AC
2019-06-03 15:07:13
int main () {
//freopen (".inp", "r", stdin);
//freopen (".out", "w", stdout);
cin.sync_with_stdio (0);
cout.sync_with_stdio (0);
cin >> n;
for (int i = 1; i <= n; ++ i) {
cin >> a[i];
}
build (1, 1, n);
cin >> m;
while (m --) {
int x, y;
cin >> x >> y;
cout << get (1, 1, n, x, y).first.first << "\n";
}
}

Last edit: 2019-06-03 15:07:39
2018-11-18 10:29:32
Code Full Đé* AC
2018-11-02 11:49:04
CNTT 1 đấm AC :v
2018-11-02 11:46:38
CYB
2017-12-07 02:26:52
ez như 1 trò đùa
2017-11-17 14:46:45
xem lời giải chi tiết:
https://vietcodes.github.io/code/114/
2017-08-22 20:17:09 Ðặng Minh Tiến
https://kienthuc24h.com/gss-spoj-doan-con-co-tong-lon-nhat/
2016-12-18 04:36:23
sau 1 thời trẩu thì đã ac mất logn đấm thôi
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.