GSS1 - Can you answer these queries I
You are given a sequence A[1], A[2] ... A[N] . ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ). A query is defined as follows:
Query(x, y) = Max { a[i] + a[i+1] + ... + a[j] ; x ≤ i ≤ j ≤ y }.
Given M queries, your program must output the results of these queries.
Input
- The first line of the input file contains the integer N.
- In the second line, N numbers follow.
- The third line contains the integer M.
- M lines follow, where line i contains 2 numbers xi and yi.
Output
Your program should output the results of the M queries, one query per line.
Example
Input: 3 -1 2 3 1 1 2 Output: 2
hide comments
|
faiz:
2015-05-21 13:12:01
wow just solve this question amazing problem |
|
LazarusLong:
2015-05-13 16:44:32
For people with a case-sensitive brain (like me), the problem statement should be:
|
|
Michael Harvey:
2015-05-08 01:37:10
For c++, I had to use scanf/printf to get it fast enough to pass, even with a good algorithm. |
|
Stanislav Zholnin:
2015-04-24 00:05:07
Limit on M is large enough to make O(mn) algorithm useless. Need O(n + m *log(n)) Last edit: 2015-04-24 00:06:40 |
|
bayram:
2015-04-20 06:18:48
What's limit of M? |
|
zorkan:
2015-04-02 23:47:01
I dont understand this question.
|
|
xxbloodysantaxx:
2015-03-28 18:01:35
WOw man...
|
|
codedog:
2015-02-02 11:00:42
if the number are -1 -2 -3 then should the max be -1 in the total array? |
|
Demjan:
2012-08-10 17:22:39
Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y } means you are given numbers x and y, you have to find numbers i and j ( where x <= i <= j <= y ) such that sum a[i]+a[i+1]+...+a[j-1]+a[j] is maximized |
| Added by: | Nguyen Dinh Tu |
| Date: | 2006-11-01 |
| Time limit: | 1s |
| Source limit: | 5000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
RSS