Submit | All submissions | Best solutions | Back to list |
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
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 |
hide comments
|
||||||||||||||
2016-01-11 15:40:08
Getting WA with judge 9 |
||||||||||||||
2015-12-25 07:35:45
no empty subset |
||||||||||||||
2015-12-25 07:35:01
quite tricky... |
||||||||||||||
2015-12-23 17:04:08 anshal dwivedi
uff! after 3 hours debugging finally got AC........ :) |
||||||||||||||
2015-12-16 18:28:11 MAYANK NARULA
To think the problem designer could have come this far in thinking ahead !!!.....Finally solved it... |
||||||||||||||
2015-12-08 21:56:50 m.ajaj94
This problem really taught me a lot though one simple mistake caused me to submit 12 WAs :/ |
||||||||||||||
2015-11-29 06:51:37
If the aeeay is 1-inexed how is the output of the sample 2 ? |
||||||||||||||
2015-11-26 09:04:06
Learnt a load of new things |
||||||||||||||
2015-11-15 20:33:35
Can't this be solved using maximum subarray algorithm from CLRS? |
||||||||||||||
2015-10-21 02:14:27
The time limit is per test case and it is very tight, so you don't want to use an buffered output otherwise you'll get a TLE. Last edit: 2015-10-25 22:14:08 |