Submission #37391338

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5,M=2e6+5;
int dep[N],tot=1,en,linkk[N];
struct Edge{int y,z,nex;}e[M*2];
bool bfs(){
	memset(dep,-1,sizeof(dep));
	queue<int> q;
	dep[0]=0;q.push(0);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=linkk[x];i;i=e[i].nex){
			int y=e[i].y,z=e[i].z;
			if(dep[y]>=0||!z)continue;
			dep[y]=dep[x]+1;q.push(y);
		}
	}
	return dep[en]>=0;
}
int dfs(int x,int in){
	if(x==en)return in;
	int out=0;
	for(int i=linkk[x];i&&in;i=e[i].nex){
		int y=e[i].y,z=e[i].z;
		if(!z||dep[y]!=dep[x]+1)continue;
		int t=dfs(y,min(in,z));
		e[i].z-=t,e[i^1].z+=t,in-=t,out+=t;
	}
	if(!out)dep[x]=-1;
	return out;
}
void ling(int x,int y,int z){e[++tot]=(Edge){y,z,linkk[x]};linkk[x]=tot;}
void add(int x,int y,int z){ling(x,y,z),ling(y,x,0);}
int _,L,R;
int main(){
	cin>>L>>R;en=(L+R+1)*105;
	for(int i=1,v;i<=L;i++){
		add(0,i*105+100,1e9);cin>>v;
		for(int j=1;j<=100;j++)add(i*105+j,i*105+j-1,v*j);
	}
	for(int i=1,v;i<=R;i++){
		add((i+L)*105+100,en,1e9);cin>>v;
		for(int j=1;j<=100;j++)add((i+L)*105+j-1,(i+L)*105+j,j*v);
	}
	for(int i=1;i<=L;i++)for(int j=1,v;j<=R;j++){
		cin>>v;
		for(int l=0;l<=100;l++){
			int r=v-l-1;
			if(r>=0)add(i*105+l,(j+L)*105+r,1e9);
		}
	}
	int ans=0;
	while(bfs())ans+=dfs(0,1e9);
	cout<<ans<<'\n';
}

Submission Info

Judge Result