手作巧克力
题目描述
小戾对身边所有人的说法，都是从超市买来的巧克力。就像是如果被别人发现是他亲手制作的，他的心盛满了的什么就会倾倒出来些许一般。
比如说，上个年头他许下的心愿，就是能为LCT做很久很久的巧克力。
他打开冰箱，拿出了制作巧克力的模具。这是一个一次性能够做\(N×M\)块巧克力的模具。有的方格底部相较于顶端是边长较小的正方形，这样制作出的巧克力就可以拥有键盘一般的形状；有的方格底部突出了一块镜面翻转后的字母形状，这样制作出的巧克力表面就会凹下去形成一个字母。不同方格内部图案的高度和所占体积都是不同的。具体而言，位于第i行第j列的方格内部的是一个高度为\(h_{i,j}\)的体积为\(v_{i,j}\)的立体图形。
小戾融化好了\(L\)毫升的巧克力，当然他并不需要将这L毫升巧克力全部倒入模具。他想要制作的巧克力需满足以下几个条件：
如果他最终倒入\(x\)毫升的巧克力，那么需要满足\(0≤x≤L\)。
巧克力会在模具内部自由流淌，最终达到在所有的格子中巧克力液面等高的情况。由于小戾希望所有的图案都能够完整，所以他希望液面能够不低于所有格子中内部图案的高度。注意，每个空的方格底面都是一个\(1cm×1cm\)的正方形，在这种情况下，倒入y毫升的巧克力之后液面高度就为y。然而有的格子内部包含图案，而图案占\(v_{i,j}cm^3\)的体积，因此当液面高度\(H>h_{i,j}\)时，该格子内部所注入的巧克力为\((H?v_{i,j})\)ml。
小戾希望最终巧克力的液面高度为整数。
请你判断是否存在满足上述条件的方法，如果有，请你找到最大的液面高度。（以厘米为单位）
输入格式
第一行三个数\(N,M,L\)，意义如题面所示。
接下来一个\(N\)行\(M\)列的矩阵，第i行第j列的元素hi,j表示该方格底部立体图形的高度。
接下来一个\(N\)行\(M\)列的矩阵，第i行第j列的元素vi,j表示该方格底部立体图形的体积。
保证\(0≤v_{i,j}≤h_{i,j}≤10^9\)。
输出格式
如果不存在满足条件的方案，输出一行-1。否则输出最大的液面高度。
样例输入1
2 2 19
0 2
1 0
0 1
1 0
样例输出1
5
样例解释
证明5的合法性：
首先5不低于所有格子的\(h\)，所以合法
其次，左上角的格子需要倒入5毫升巧克力，右上角须要倒入4，左下角需要倒入4，右下角需要倒入5，才能到达液面高度为5。一共需要18毫升巧克力，巧克力足够。
6的不合法大家可自行验证。
样例输入2
4 5 23
7 4 5 0 4
6 5 2 7 0
8 4 8 9 0
0 9 9 8 4
0 1 4 0 1
6 0 1 0 0
8 1 8 7 0
0 7 4 4 0
样例输出2
-1
样例输入3
4 5 209
3 3 1 7 0
6 8 5 3 2
5 6 3 7 5
4 3 1 9 7
1 3 1 6 0
1 4 4 1 0
4 5 3 5 1
0 0 0 1 3
样例输出3
12
题目限制
时间限制：1000ms
空间限制：512MB
对于50%的数据，\(N,M,L,h_{i,j},v_{i,j}≤10\)。
对于100%的数据，\(N,M≤500, 0≤v_{i,j}≤h_{i,j}≤10^9, 0≤L≤10^{18}\)。
考虑二分。
二分的左边界一定是最大的h，然后二分判断\(x\)可不可行时用\(x\)减去\(v_{i,j}\)的和即可。
最后看二分出来有没有小于所有的h的最大值。
#include
using namespace std;
long long l,r,md,L,R,h[505][505];
int n,m,v[505][505];
int check(long long x)
{
long long ret=x*n*m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ret-=v[i][j];
return ret<=L;
}
int main()
{
scanf("%d%d%lld",&n,&m,&L),r=1e13;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%lld",&h[i][j]),l=max(l,h[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",v[i]+j);
R=l;
while(l<=r)
{
md=l+r>>1;
if(check(md))
l=md+1;
else
r=md-1;
}
if(r