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
marshmellow:
2017-03-19 09:55:24
input:
|
|
scorpion_ajay:
2017-03-19 07:54:59
@anurag_333
|
|
jeelapamy:
2017-03-13 18:05:59
hallelujah thank you god AC in one go Last edit: 2017-03-13 18:06:13 |
|
anurag_333:
2017-03-08 19:39:08
can it be done by kadane's algorithm????\
|
|
vladimira:
2017-02-25 14:24:01
Are there any succesful python submissions, cos mine give only TLEs ? |
|
da_201501443:
2017-02-22 19:12:42
in java, I used segment tree and get TLE. How to make accurate my code?? Anybody please help me.
|
|
yeguzi2020:
2017-02-16 14:22:32
In C++, use cin with fast IO get TL, use scanf get AC. LOL |
|
deepanshu_2015:
2017-02-12 10:12:32
getting wa after test case 9 |
|
ashishsb95:
2017-01-17 19:43:38
using scanf and printf made a difference! |
|
dante_smit_98:
2017-01-16 16:37:16
getting WA after test case 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 |