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.|

QTSEQ - Dãy số QT

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/qtseq


Một vụ tai nạn giao thông vừa xảy ra ngoài phố. Mọi người tò mò chen lấn vòng trong vòng ngoài để xem. Rất đông người xem vụ tai nạn như: khanh_can_k7, nhungngoisao, chicuong123, harry_porter_7, mr_ntt, manhboyak6. Một anh đến chậm không tài nào vào xem được. Tức quá, anh ta liền hét toáng lên:

- Tôi là bố kẻ bị nạn đây!

Mọi người kinh ngạc quay lại nhìn và vội vã giãn ra cho anh ta vào. "Kẻ bị nạn" là một... chú chó vừa bị xe cán chết.

Ngại ngùng, anh ta chạy về nhà, than khóc. Và ông tiên hellosirius hiện ra ban cho anh ta 1 điều ước. Anh ta ước rằng mọi người trên thế giới sẽ quên hết mọi chuyện trong hôm nay. Tuy nhiên, theo định luật bảo toàn năng lượng cũng như định luật bảo toàn tính mạng ông tiên buộc chú phải giải bài toán sau mới giúp chú thực hiện điều ước. Nhanh chóng chú giải được bài toán ông đưa ra tuy nhiên, lần này ông buộc chú phải chiến đấu với hiệp sĩ đẹp trai n_cqtblackstar. Để chiến thắng hiệp sĩ cách duy nhất là giải được bài toán hiệp sĩ đưa ra ( vì hiệp sĩ không những đẹp trai, học giỏi mà còn khỏe mạnh vô đối nữa ). Đề bài của hiệp sĩ như sau:

Cho dãy số nguyên A gồm N phần tử A1,A2,...,An. Tìm cặp chỉ số i,j thỏa mãn:

DSEQ = |(A1 + A2 + ... + Ai) - (Aj + Aj+1 + ... + An)| đạt giá trị lớn nhất (với 1 ≤ i < j ≤ N).

Hãy giúp anh bạn khốn khổ của chúng ta hoàn thành điều ước!

Input:

Dòng đầu là số nguyên dương N; (2 ≤ N ≤ 106).  

Dòng tiếp theo chứa N số nguyên A1, A2, …, An; (|Ai|<109), các số cách nhau một dấu cách.

Output:

Gồm một dòng chứa 2 số nguyên là DSEQ lớn nhất tìm được( do hiệp sĩ n_cqt yêu cầu ) và số cặp chỉ số thỏa mãn (hai số cách nhau một dấu cách) ( do hiệp sĩ blackstar yêu cầu )

Example:

Input:

5

1 -2 3 -4 -7

Output:

13 1

Lưu ý: 50% số test N≤5000.


Được gửi lên bởi:continue......
Ngày:2012-03-29
Thời gian chạy:0.200s
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ừ: ADA95 ASM64 GAWK BASH BF CLPS LISP sbcl LISP clisp D ERL FSHARP FORTRAN GO GOSU HASK ICON ICK LUA NEM NICE OCAML PERL PERL6 PHP PIKE PRLG-swi PYTHON PYPY PYTHON3 RUBY RUST SCALA SCM guile SCM qobi SED ST TCL WHITESPACE
Nguồn bài:Trịnh Minh Nhật - Khóa 8

hide comments
2012-03-30 10:03:50 Noyethug
test hiểm nhỉ..:))
PS add thêm test sao k chấm lại toàn bộ nhỉ..

Last edit: 2012-03-30 10:26:22
2012-03-30 08:32:11 continue......
test với N=10^6 của mình cũng là 1 trường hợp nếu không xử lí tốt thì có thể không qua nhưng mình xem rank thì vẫn có nhiều người đã qua với chỉ 0,6-0,8(s) thôi bạn ạ

Last edit: 2012-03-30 14:44:53
2012-03-30 08:23:43 Noyethug


Last edit: 2012-03-31 08:56:33
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.