好神的题啊 我不会做啊 AwD orzz
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; typedef long long ll; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b; } const int N=505*505; int n; int p[505][505]; int l[N],r[N],K[N],a[N],idx[N]; ll sum; inline bool cmp(int a,int b){ return K[a]<K[b]; } int main(){ int _n,x; freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(_n); for (int i=1;i<=_n;i++) p[i][i]=++n; for (int i=1;i<=_n;i++) for (int j=i+1;j<=_n;j++) p[i][j]=p[j][i]=++n; for (int i=1;i<=n;i++) l[i]=-1<<30,r[i]=1<<30,K[i]=0; for (int i=1;i<=_n;i++) for (int j=1;j<=_n;j++) read(x),K[p[i][j]]+=x; for (int i=1;i<=_n;i++) K[i]<<=1; for (int i=1;i<=_n;i++) for (int j=1;j<=_n;j++) read(x),l[p[i][j]]=max(l[p[i][j]],x); for (int i=1;i<=_n;i++) for (int j=1;j<=_n;j++) read(x),r[p[i][j]]=min(r[p[i][j]],x); for (int i=_n+1;i<=n;i++) l[i]<<=1,r[i]<<=1; for (int i=1;i<=n;i++) idx[i]=i; sort(idx+1,idx+n+1,cmp); for (int i=1;i<=n;i++) a[i]=r[i],sum+=r[i]; for (int i=1;i<=n;i++){ int x=idx[i]; if (sum>a[x]-l[x]) sum-=a[x]-l[x],a[x]=l[x]; else if (x<=_n || sum%2==0){ a[x]-=sum; break; }else{ a[x]-=sum; int p=i,q=i; while (q<=n && (idx[q]>_n || a[idx[q]]==l[idx[q]])) q++; while (p>=1 && (idx[p]>_n || a[idx[p]]==r[idx[p]])) p--; if (!p|| (q<=n && K[idx[q]]-K[x]<K[x]-K[idx[p]])) a[x]++,a[idx[q]]--; else a[x]--,a[idx[p]]++; break; } } ll Ans=0; for (int i=1;i<=n;i++) Ans+=(ll)a[i]*K[i]; printf("%lld\n",Ans/2); return 0; }