QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#388588 | #6113. Window Arrangement | MladenP# | TL | 2ms | 10892kb | C++14 | 2.8kb | 2024-04-13 17:10:48 | 2024-04-13 17:10:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define maxn 52
#define maxt 200000
int n,m;
int p[maxn][maxn];
int w[maxn][maxn];
int t;
struct eg{
int v;
int iv;
int ca;
int co;
};
vector<eg> g[maxt];
void add_edge(int u,int v,int ca,int co) {
g[u].push_back({v,g[v].size(),ca,co});
g[v].push_back({u,g[u].size()-1,0,-co});
}
long long inf=1e18;
long long lvl[maxt];
pair<int,int> par[maxn];
bool ex[maxt];
void init() {
for(int i=0;i<=t;i++) {
lvl[i]=inf;
}
lvl[0]=0;
}
int q[maxt];
int sz=0;
void bf() {
sz=0;
q[sz++]=0;
ex[0]=true;
//cout<<"in"<<endl;
for(int it=0;it<sz;it++) {
int u=q[it];
ex[u]=false;
for(int i=0;i<g[u].size();i++) {
int v=g[u][i].v;
int j=g[u][i].iv;
if(g[u][i].ca && lvl[u]+g[u][i].co<lvl[v]) {
lvl[v]=lvl[u]+g[u][i].co;
par[v]={u,i};
if(!ex[v]) {
q[sz++]=v;
ex[v]=true;
}
}
}
}
//cout<<"out"<<endl;
}
long long mcmf() {
int r=0;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
r+=w[i][j];
}
}
init();
bf();
long long ret=0;
while(lvl[t]!=inf) {
int v=t;
while(v!=0) {
int u=par[v].first;
int i=par[v].second;
int j=g[u][i].iv;
ret+=g[u][i].co;
g[u][i].ca-=1;
g[v][j].ca+=1;
v=u;
}
init();
bf();
}
return ret;
}
int main() {
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
scanf("%d",&p[i][j]);
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
scanf("%d",&w[i][j]);
add_edge(0,(i-1)*m+j,w[i][j],0);
add_edge((i-1)*m+j,n*m+(j-1)*(n+1)+i,1,0);
add_edge((i-1)*m+j,n*m+(j-1)*(n+1)+i+1,1,0);
add_edge((i-1)*m+j,n*m+(n+1)*m+(i-1)*(m+1)+j,1,0);
add_edge((i-1)*m+j,n*m+(n+1)*m+(i-1)*(m+1)+j+1,1,0);
}
}
t=n*m+(n+1)*m+(m+1)*n+1;
for(int j=1;j<=m;j++) {
add_edge(n*m+(j-1)*(n+1)+1,t,1,0);
add_edge(n*m+(j-1)*(n+1)+1,t,1,0);
for(int i=1;i<=n;i++) {
add_edge(n*m+(j-1)*(n+1)+i+1,t,1,0);
add_edge(n*m+(j-1)*(n+1)+i+1,t,1,p[i][j]*p[i+1][j]);
}
}
for(int i=1;i<=n;i++) {
add_edge(n*m+(n+1)*m+(i-1)*(m+1)+1,t,1,0);
add_edge(n*m+(n+1)*m+(i-1)*(m+1)+1,t,1,0);
for(int j=1;j<=m;j++) {
add_edge(n*m+(n+1)*m+(i-1)*(m+1)+j+1,t,1,0);
add_edge(n*m+(n+1)*m+(i-1)*(m+1)+j+1,t,1,p[i][j]*p[i][j+1]);
}
}
printf("%lld",mcmf());
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10892kb
input:
4 3 1 7 10 7 2 8 7 9 10 4 6 4 3 3 3 3 2 4 4 3 4 2 2 3
output:
178
result:
ok 1 number(s): "178"
Test #2:
score: 0
Accepted
time: 2ms
memory: 9584kb
input:
4 3 2 2 9 9 8 4 8 4 5 7 5 2 0 1 0 1 0 1 0 0 1 0 1 0
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: -100
Time Limit Exceeded
input:
20 20 755 344 600 54 516 407 657 429 565 185 90 323 449 464 872 138 404 500 196 111 666 191 824 98 505 538 949 801 266 861 984 957 396 851 496 147 225 451 874 380 536 200 581 397 305 514 351 416 228 763 566 442 618 131 527 651 954 757 226 129 286 608 819 477 891 22 19 747 565 704 198 703 736 8 835 1...