ZSEQ - ZSequence
You will be given a sequence A containing N positive integers, a1, a2 ... aN.
Let S(i, j) = ai + ai + 1 + ... + aj, if i <= j.
You should find K - 1 indexes, m1 < m2 < ... < mK - 1 such that lb1 <= S(1, m1) <= ub1 ... lbi <= S(mi - 1 + 1, mi) <= ubi and lbK <= S(mK - 1 + 1, N) <= ubK.
If there are multiple solution, print the first lexicographically.
Input
The first line of the standard input contains two space-separated integers N (2 <= N <= 5 000) and K (1 <= K - 1 <= N - 1). Next N lines contain integers a1, a2 ... aN, respectively, 1 <= ai <= 105.
i-th of the next K lines contain integers lbi and ubi, 1 <= lbi <= ubi <= 109.
Output
On the first line of the standard output you should print space-separated K - 1 indices of the solution as already explained. If such solution does not exist, you should print only one integer -1.
Example
Input: 4 3 1 2 3 4 1 3 2 4 3 10 Output: 1 2
Input: 4 3 1 2 3 4 1 3 2 4 3 4 Output: 2 3
Input: 4 3 1 2 3 4 1 3 2 4 3 3 Output: -1
hide comments
Shaka Shadows:
2010-10-04 19:32:12
Even when there is no point in setting a customized memory limit, here memory is not what we have to worry about (except for Java solutions of course). Time limit is the big deal here. Thanks Slobodan, if we take away the memory stuffs, I do think actually it is a good problem. |
|
Slobodan:
2009-10-13 00:52:40
Well, I hope you will forgive me this time. I already set memory limit and some members maybe spent more time trying to solve with that constraint.
|
|
Nikhil Garg:
2009-10-08 09:49:14
We can change the amount of memory allocated for java program but that cant be done from inside a program. That has to be set at the JVM settings on command prompt that too with sudo power only. So this is as good as saying - problem is not solvable in java ! |
|
[Trichromatic] XilinX:
2009-09-29 14:42:00
Mmm, I do agree with Jelle van den Hooff. I've got Accepted. |
|
Slobodan:
2009-09-20 14:07:39
> The question is why would you want a memory limit?
|
|
Jelle van den Hooff:
2009-09-20 13:55:49
Case in point: 5000^2 _bits_ is only 3 megabytes, so I just don't get the limit. |
|
Jelle van den Hooff:
2009-09-20 13:53:54
The question is why would you want a memory limit? If the difficulty in the problem comes from having a strict memory limit then the problem is bad. Nearly all of the SPOJ problems don't have a memory limit (even the ones taken from other judges). |
|
Slobodan:
2009-09-20 11:29:10
Well, is there a way to specify memory limit for certain language? |
|
[Trichromatic] XilinX:
2009-09-20 10:48:31
The memory limit is useless. For some languages like Java, the memory used is always ~200MB, even though the program just solves problem TEST. |
Added by: | Slobodan |
Date: | 2009-09-19 |
Time limit: | 0.100s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO |
Resource: | Z-Trening, own problem |