SPOJ.com - Problem GSS

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

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/gss

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

Submit solution!

Đượ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

2024-08-09 06:38:42
bài segment tree
code: https://ideone.com/KuEMfC

2021-05-27 18:00:49
Tham khảo: https://vnspoj.github.io/problems/GSS

2020-07-22 18:36:45
TranTrungKienGoldIOI2021

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

Giải bài trực tuyến

GSS - Đoạn con có tổng lớn nhất

Input

Output

Example