QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #67728 | #4786. Balance | A_zjzj | WA | 6ms | 3448kb | C++14 | 1.4kb | 2022-12-11 15:27:53 | 2022-12-11 15:27:56 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;using ll=long long;const int N=55,INF=1e9;
int n,a[N][N],b[N][N],A[N],B[N],tag[N][N];
int calc(int x){
b[1][1]=x;for(int i=2;i<=n;i++)b[i][1]=a[i][1],b[1][i]=a[1][i];
for(int i=1;i<=n;i++)A[i]=B[i]=0;memset(tag,0,sizeof tag);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)tag[i][j]=b[i][1]+b[1][j]<x+a[i][j],A[i]+=tag[i][j],B[j]+=tag[i][j];
for(;;){
int p=1,q=1;for(int i=2;i<=n;i++)if(A[i]>A[p])p=i;for(int i=2;i<=n;i++)if(B[i]>B[q])q=i;
if(!A[p]&&!B[q])break;
if(A[p]>B[q]){
int mn=INF;for(int i=1;i<=n;i++)if(tag[p][i])mn=min(mn,x+a[p][i]-b[p][1]-b[1][i]);
b[p][1]+=mn;for(int i=1;i<=n;i++)if(tag[p][i]&&b[p][1]+b[1][i]>=x+a[p][i])tag[p][i]=0,A[p]--,B[i]--;
}else{
int mn=INF;for(int i=1;i<=n;i++)if(tag[i][q])mn=min(mn,x+a[i][q]-b[i][1]-b[1][q]);
b[1][q]+=mn;for(int i=1;i<=n;i++)if(tag[i][q]&&b[i][1]+b[1][q]>=x+a[i][q])tag[i][q]=0,A[i]--,B[q]--;
}
}int sum=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)sum+=b[i][1]+b[1][j]-x;return sum;
}
int main(){
cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];
int l=a[1][1],r=3.5e4,ml,mr;for(;l+10<r;)ml=(l+l+r)/3,mr=(l+r+r)/3,calc(ml)<calc(mr)?r=mr:l=ml;
int ans=INF,id=-1;for(int i=l,x;i<=r;i++)if(x=calc(i),x<ans)ans=x,id=i;calc(id);cout<<ans<<endl;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cout<<b[i][1]+b[1][j]-b[1][1]<<"\n "[j<n];return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3364kb
input:
4 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
output:
16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
result:
ok correct plan, good job!
Test #2:
score: -100
Wrong Answer
time: 6ms
memory: 3448kb
input:
24 20594 15420 1258 6283 18795 7007 20323 16605 27476 270 2082 5286 32911 30847 17237 14187 9258 26749 27575 8042 2690 25493 23540 30506 15252 21600 26878 32384 22641 12550 29190 28725 33837 7235 6316 1318 10773 4177 6535 33628 31431 19567 25294 22712 18861 16725 25214 12950 29777 22466 16743 2033 3...
output:
19025496 32802 33948 42365 34652 39935 37622 39775 33149 36105 36833 37644 34124 32965 35200 35994 35896 35660 37777 36161 28357 35298 36760 32939 35309 30534 31680 40097 32384 37667 35354 37507 30881 33837 34565 35376 31856 30697 32932 33726 33628 33392 35509 33893 26089 33030 34492 30671 33041 299...
result:
wrong answer the sum of the elements in your matrix is 19025496, but jury's plan is 18759816