|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
II Copa MATCOM ACM-ICPCEnded |
A - Intervalo de Suma Máxima
Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)
Dada una lista de $N$ enteros $\{x_1, x_2, \dotsc, x_N\}$ y un conjunto de $Q$ preguntas definidas como $[a, b]$ usted debe calcular el intervalo de suma máxima que está completamente contenido en $[a, b]$. En otras palabras, dado dos enteros $a$ y $b$ $(1 \le a \le b \le N)$ usted debe buscar el intervalo $[i, j]$ tal que $a \le i \le j \le b$ y maximice $x_{i} + x_{i+1} + \dotsb + x_{j}$.
Input
Línea 1
: Un único entero $N$ $(1 \le N \le200000)$.
Línea 2 : $N$ enteros separados por espacio $x_1, x_2, \dotsc, x_N$ $(|xi| ≤ 10000)$.
Línea 3 : Un único entero $Q$ $(1 \le Q \le200000)$.
Línea 4… Q + 3 : Dos enteros $a$ y $b$ $(1 \le a \le b \le N)$ por línea.
Línea 2 : $N$ enteros separados por espacio $x_1, x_2, \dotsc, x_N$ $(|xi| ≤ 10000)$.
Línea 3 : Un único entero $Q$ $(1 \le Q \le200000)$.
Línea 4… Q + 3 : Dos enteros $a$ y $b$ $(1 \le a \le b \le N)$ por línea.
Output
Línea 1…Q
: Por cada pregunta imprima el valor del intervalo de suma máxima contenido completamente en $[a, b]$.
Sample test(s)
Input
10
4 -2 -1 5 -1 0 10 -9 8 -3
5
1 1
2 2
1 10
3 5
4 9
Output
4
-2
15
5
14
Hints
Considere el caso en el ejemplo:
|
Pregunta |
Intervalo De Suma Máxima |
Suma |
|
1 1 |
1 1 |
4 |
|
2 2 |
2 2 |
-2 |
|
1 10 |
1 7 |
4+(-2)+(-1)+5+(-1)+0+10 = 15 |
|
3 5 |
4 4 |
5 |
|
4 9 |
4 7 |
5+(-1)+0+10=14 |