I had a different approach to H that results in very short, but incorrect code (114044595, 114044982). I also have a few versions which I don't know how to hack (114142853, 114141339, 114141392). Can anyone hack these or prove they're correct?
The main idea is to use strong LP duality: the problem is unsatisfiable if and only if there is some linear combination of the input constraints such that all variables cancel and the constants give a contradiction (e.g. $$$0 \le -1$$$). We can try to simplify this by only checking all "extremal" feasible linear combinations, i.e. linear combinations on the convex hull of all linear combinations whose variables completely cancel.
Here, I came up with the (false) hypothesis that any such extremal linear combination must include 2 "neighboring" constraints which we can treat as a relaxation, e.g. we use both $$$y_{i-1}^+$$$ and $$$z_{i}^+$$$; these can be "merged" into a (possibly tighter) constraint on $$$y_{i}^+$$$ which we will use instead. This is not quite true, and the counterexample can be seen in https://codeforces.com/contest/1517/hacks/731593/test.
Assuming this hypothesis, I made another assumption that, similar to out-of-order Floyd-Warshall, we may be able to simply do all relaxations and loop up to either $$$O(1)$$$ or $$$O(\log n)$$$ times in order to find the cycle. I don't have a proof, but it feels plausible (after the $$$k$$$th iteration, our relaxations must include all paths with at most $$$2^k$$$ zig-zags or something?).
Now, you might've noticed that 114044982 fails with TLE instead of WA; if it were allowed to run for long enough, it would actually print the correct answer. This is because my hypothesis is false for extremal linear combinations, but I think it's true that there must be some negative linear combination which can be attained via these relaxations. This is because we can take the extremal negative cycle, multiply it by a large number, and add any positive cycle including the desired neighbors. Thus, it seems like my code is guaranteed to finish in $$$O(N * MAXVALUE)$$$ or so.
Now for the challenge: I now have a new hypothesis: if, after running for some number of iterations, the relaxations have not stabilized, then there must be a negative cycle and we can just print "NO". That's the basis for my 3 new submissions: 114142853 (60 loops), 114141339 (1000 loops), 114141392 ($$$N$$$ loops). Can anyone hack these or prove them correct?
Is this the reason for multiple tags.. hmm...
Hacked. I forced $$$b$$$ to be $$$a_1,0,a_2,0,...,a_k,0$$$ for some array $$$a$$$ by forcing $$$b_1=a_1$$$ and $$$b_{2x}=0$$$ for all $$$x$$$ and using $$$z$$$ to make restrictions on $$$a_i+a_{i+1}$$$ for all $$$i$$$. Your solutions do 1 relaxation per element of $$$a$$$, so that hacks your solutions.
Too easy for dori
This is an interesting approach! dorijanlendvaj's nice hack shows that you sometimes need to do a long chain of relaxations of the form $$$y_i \leftarrow x_i - x_{i-1}$$$ followed by $$$y_{i+1} \leftarrow y_i + z_i$$$ followed by $$$x_{i+1} \leftarrow x_i + y_{i+1}$$$ etc (using the indexing of the problem statement). This hacks your solution because you have one loop for each of these 3 kinds of relaxations. I modified it to do all kinds of relaxation in the same loop. Submission 114202015 currently gets AC while only going forwards + backwards 3 times.
I don't know if this solution is actually correct. Maybe another hack (where the correct answer is "YES") would require more loops for the relaxations to stabilise? I'm also not convinced by your argument that these relaxations are sufficient to determine the answer... More precisely, supposing there is no relaxation on the input, can you prove that the answer is "YES"? You've pointed out that a stronger hypothesis in this direction is false. A minimal counterexample is where you have $$$z_2^+ + 2z_3^+ + z_4^+ + x_0^+ - 2x_2^- + x_4^+ < 0$$$. These bounds all cancel (unless I've made a typo), but there is no "neighbouring" pair.