萌新刚学 oi，开道小清新题找找感觉。
首先求出每个人最终有的卡牌数 \(X\)，以及每个人需要收到的卡牌数 \(c_i\)。
考虑怎么计算一个人 \(i\) 的答案，假设我们希望第 \(i\) 个人最多的卡牌为类型 \(j\)，那么得尽可能将类型 \(j\) 的卡牌给 \(i\)——显然我们最多能给 \(\min(b_j,c_i)\) 个卡牌 \(j\) 给第 \(i\) 个人。这样第 \(i\) 个人每种卡牌个数的最大值就确定了，这样我们的目标变为让另外 \(n-1\) 个人每种卡牌个数的最大值尽可能小。考虑二分答案 \(mid\)，思考如何检验一个 \(mid\) 是否可行：
-
如果存在 \(k\ne i,0\le j\le 3\) 满足 \(a_{i,j}>mid\)，那么一定不可行。
-
否则考虑网络流建模。新建源点 \(S\) 和汇点 \(T\)，以及 \(x_1\sim x_4,y_1\sim y_n\)，然后连边：
- \(S\to x_k\)，容量 \(b_i\)。
- \(x_k\to y_j(j\ne i)\)，容量 \(mid-a_{j,k}\)。
- \(y_j\to T(j\ne i)\)，容量 \(c_j\)。
最后检验最大流是否为 \(\sum\limits_{i\ne j}c_j\) 即可。
显然每次建一次图是没法接受的。考虑最大流最小割定理，我们枚举哪些与源点相连的边没被割掉，那么割掉剩余的边的代价就是 \(\sum\limits_{i\ne j}\min(c_j,\sum\limits_{x\in S}mid-a_{j,x})\)，割掉与 \(S\) 相连的边的代价是 \(\sum\limits_{x\notin S}b_x\)。显然，后者是容易计算的，而对于前者而言，如果我们将所有 \(j\) 按照 \(c_j+\sum\limits_{x\in S}a_{j,x}\) 从大到小排序后，那么取到后者的是一段前缀，二分即可。
时间复杂度 \(O(n·2^4·4·\log^2V)\)，由于常数小可以通过。
const int MAXN=5e4;
int n,a[MAXN+5][4],b[4],c[MAXN+5],mxa[MAXN+5];ll sum=0,tot=0;
vector<pair<ll,int> >val[16];
vector<ll>pre[16],suf[16];
bool check(int x,int v){
for(int S=1;S<16;S++){
ll sum=0,s=0;
for(int i=0;i<4;i++)if(~S>>i&1)sum+=b[i];
int L=0,R=n-1,p=n,cs=__builtin_popcount(S);
while(L<=R){
int mid=L+R>>1;
if(val[S][mid].fi<=v*cs)p=mid,R=mid-1;
else L=mid+1;
}
if(p)sum+=1ll*p*v*cs-pre[S][p-1];
sum+=suf[S][p];
for(int i=0;i<4;i++)if(S>>i&1)s+=v-a[x][i];
sum-=min(s,(ll)c[x]);
if(sum<tot-c[x])return 0;
}return 1;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)for(int j=0;j<4;j++)scanf("%d",&a[i][j]),sum+=a[i][j];
for(int i=0;i<4;i++)scanf("%d",&b[i]),sum+=b[i];
for(int i=1;i<=n;i++){
c[i]=sum/n;
for(int j=0;j<4;j++)c[i]-=a[i][j];
tot+=c[i];
}
for(int i=1;i<=n;i++)for(int j=0;j<4;j++)chkmax(mxa[i],a[i][j]);
multiset<int>st;
for(int i=1;i<=n;i++)st.insert(mxa[i]);
for(int S=1;S<16;S++){
for(int i=1;i<=n;i++){
ll sum=c[i];
for(int j=0;j<4;j++)if(S>>j&1)sum+=a[i][j];
val[S].pb(mp(sum,i));
}
sort(val[S].begin(),val[S].end());
reverse(val[S].begin(),val[S].end());
pre[S].resize(n,0);suf[S].resize(n+1,0);
for(int i=0;i<n;i++){
int id=val[S][i].se;
if(i)pre[S][i]=pre[S][i-1];
for(int j=0;j<4;j++)if(S>>j&1)pre[S][i]+=a[id][j];
}
for(int i=n-1;~i;i--){
int id=val[S][i].se;
suf[S][i]=suf[S][i+1]+c[id];
}
}
for(int i=1;i<=n;i++){
int mx=0;st.erase(st.find(mxa[i]));
for(int j=0;j<4;j++){
int can=min(b[j],c[i]),v=can+a[i][j];
int l=*st.rbegin(),r=v,p=v;b[j]-=can;
while(l<=r){
int mid=l+r>>1;
if(check(i,mid))p=mid,r=mid-1;
else l=mid+1;
}chkmax(mx,v-p);b[j]+=can;
}printf("%d%c",mx," \n"[i==n]);
st.insert(mxa[i]);
}
return 0;
}