MCMF? solution codeforces
MCMF? solution codeforces You are given two integer arrays aa and bb (bi≠0bi≠0 and |bi|≤109|bi|≤109). Array aa is sorted in non-decreasing order. The cost of a subarray a[l:r]a[l:r] is defined as follows: If ∑j=lrbj≠0∑j=lrbj≠0, then the cost is not defined. Otherwise: Construct a bipartite flow graph with r−l+1r−l+1 vertices, labeled from ll to rr, with all vertices having bi<0bi<0 on the left and those with bi>0bi>0 on right. For each i,ji,j such that l≤i,j≤rl≤i,j≤r, bi<0bi<0 and bj>0bj>0, draw an edge from ii to jj with infinite capacity …