Topcoder SRM #694 交流贴

Div1 900
令a[-1]=a[n]=0，记b[i]=a[i]-a[i-1](i=0,1,2,...,n)，那么每次操作(L,R,X,Y)相当于给b[L]加上一个[X,Y]内的数，同时给b[R+1]减去这个数，最后要保证b[1]=b[2]=...=b[n-1]的同时最大化b[0]，考虑建立一个网络流模型，n为源点，0为汇点，对于每个操作(L,R,X,Y)，从R+1向L连一条流量下界为X上界为Y的边，跑一个带下界最大流即可，如果没有可行流输出-1，否则输出最大流。