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
|
aryan__0406:
2020-04-09 19:34:19
@randomtree you have written wrong code that's why you are getting wrong answer.
|
|
randomtree:
2020-04-04 23:20:14
I'm using brute force and getting WA. Any suggestions? |
|
|
aryan__0406:
2020-03-26 16:21:18
A good problem on segment trees.A must solve problem. Last edit: 2020-04-09 19:32:43 |
|
rajgothi:
2020-03-26 11:42:24
misunderstanding kill my 2 hours! |
|
|
aryan__0406:
2020-03-26 10:43:26
@noob_2798 we have to find the maximum subsequence so it is necessary for them to be contiguous.
|
|
noob_2798:
2020-03-24 19:57:56
Is it necessary for the elements to be contiguous? |
|
heartless_2811:
2020-03-23 14:31:49
help me debugging this code !! I think it's failing on test case 9 https://ideone.com/5Efoaw |
|
shanto09:
2020-03-23 08:43:26
A problem worth solving! |
|
vritta:
2020-03-22 11:14:34
For the newbies you can see explanation on my blog(read the comments for explanation), copy the code on your IDE & remove unnecessary comments it will become short- <snip> Last edit: 2022-08-17 17:30:35 |
|
herrdirektor:
2020-03-17 17:00:18
solved after many attempts. Total satisfaction after solving this one
|
| 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