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
scyth3r:
2015-07-10 19:15:50
no AC Python submission..... :< |
|
Aman Agarwal:
2015-07-08 09:03:37
learned pretty nice things from this questions..Thnx for setting such a problem |
|
atg_abhishek:
2015-06-29 04:47:11
TLE for Java code, using Kadane's algorithm, any suggestions to make it pass? |
|
Arjun Verma:
2015-06-25 21:10:20
c++ , use scanf/printf |
|
Abhishek pratap singh:
2015-06-18 13:26:20
@NITIKA Increase your tree array size. |
|
Deepak Singh Tomar:
2015-06-16 23:14:22
segment_tree#1 |
|
Liquid_Science:
2015-06-15 10:28:12
Very stringent time limit for java programmers ,I guess that explains why around 15 java solution till now , Time limits should be seriously reconsidered to give other language programmers a chance |
|
silentcode:
2015-06-13 20:54:07
@anando_du : ans should be 118 for this case no?? can you please explain how did you get 111?? Last edit: 2015-06-13 20:55:32 |
|
anando_du:
2015-06-11 19:29:37
test case:
|
|
dastanforever:
2015-06-08 10:49:52
WA on judge 9:( |
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 |