link: http://community.topcoder.com/stat?c=problem_statement&pm=12294 I have found a clever iteration approach for this problem and 4ms passed(this approach is also proper for find integer optimal solution):

first build graph and get all connected component of the graph these component are monotonic between each other,so choose and solve one component and other variable value is lower_bound.

for one connected component first init the variables:satisfy sum of these variable is maxSum,and value of each is between lower_bound and upper_bound. choose any two variables a and b as main variables ,others regard as constant,then find the local optimal value of these variables,let a to be a+dx,b to be b-dx,find the value of dx that is optimal: if a and b is directly connected, it is a downward quadratic function (a+dx)*(b-dx)+C*dx+D, lower[a]<=a+dx<=upper[a] lower[b]<=b-dx<=upper[b]. otherwise it is a linear function. for every two main varibales we can choose the maximum increment of the local optimal values,and relax the chosen varibles: ans[choose_a]+=dx; ans[choose_b]-=dx; until we can't get more optiaml values compare each component of optimal value and choose the max.

this approach is much faster than editorial's O(3^n*n) and it is also proper for find integer optimal solution. complexity is O(n^2*times) times is the (times of interation,seems to be log(1.0/accurancy),not proved yet)