QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#789142#9665. Black-White Cubic Latticerotcar07AC ✓97ms4668kbC++231.6kb2024-11-27 19:24:172024-11-27 19:24:17

Judging History

你现在查看的是最新测评结果

  • [2024-11-27 19:24:17]
  • 评测
  • 测评结果:AC
  • 用时:97ms
  • 内存:4668kb
  • [2024-11-27 19:24:17]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int N=5005;
int n,m,l;
typedef long long ll;
constexpr ll inf=1e9,Inf=1e13;
constexpr int maxn=5005,maxm=1e5+5;
int s,t,tot=1,fir[maxn],to[maxm],nxt[maxm];ll val[maxm];
inline void addedge(int u,int v,ll w){++tot,nxt[tot]=fir[u],fir[u]=tot,to[tot]=v,val[tot]=w;}
inline void add(int u,int v,ll w){addedge(u,v,w),addedge(v,u,0);}
int dep[maxn],firr[maxn];
inline bool bfs(){
    memcpy(firr,fir,sizeof fir);
    memset(dep,0,sizeof dep);dep[s]=1;
    queue<int> q;q.push(s);
    while(!q.empty()){
        int p=q.front();q.pop();
        if(p==t) return 1;
        for(int i=fir[p];i;i=nxt[i])if(!dep[to[i]]&&val[i]) dep[to[i]]=dep[p]+1,q.push(to[i]);
    }
    return 0;
}
ll dfs(int p,ll res){
    if(p==t) return res;
    ll fl=0;
    for(int &i=firr[p];i;i=nxt[i])if(dep[to[i]]==dep[p]+1&&val[i]){
        ll z=dfs(to[i],min(res,val[i]));
        res-=z,fl+=z,val[i]-=z,val[i^1]+=z;
    }
    if(!fl) dep[p]=0;
    return fl;
}
int main(){
    cin>>n>>m>>l;
    vector<int> v;v.push_back(0);
    for(int i=1;i<=l*n;i++){
        string s;cin>>s;
        for(char c:s) v.emplace_back(c=='W');
    }
    s=0,t=n*m*l+1;
    ll ans=-inf*n*m*l;
    for(int i=0;i<l*n;i++){
        for(int j=1;j<=m;j++){
            int x=i*m+j,y;cin>>y;
            add(s,x,x==n*m*l?Inf:inf+(v[x]?y:0));
            add(x,t,x==1?Inf:inf+(v[x]?0:y));
            if(j<m) add(x,x+1,Inf);
            if(i%n!=n-1) add(x,x+m,Inf);
            if(i/n!=l-1) add(x,x+n*m,Inf);
        }
    }
    while(bfs()) ans+=dfs(s,1e18);
    cout<<ans<<'\n';
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3652kb

input:

2 2 2
WW
WW
BB
BB
1 1
1 1
2 2
2 2

output:

5

result:

ok single line: '5'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3520kb

input:

2 1 1
W
B
0
1

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 19ms
memory: 4548kb

input:

1 1 5000
B
W
W
W
W
W
W
W
W
B
B
B
W
B
W
B
W
B
W
W
B
W
W
B
B
W
B
B
B
B
W
W
W
W
W
W
W
B
B
B
B
B
B
B
B
B
W
B
B
W
B
B
B
W
W
B
B
W
W
W
W
W
W
W
B
B
B
B
W
B
B
W
B
W
W
W
W
W
B
B
W
B
B
W
W
B
W
B
B
B
B
W
W
W
B
B
W
B
W
W
W
W
W
B
W
B
B
B
W
W
B
W
B
B
W
B
W
B
B
B
B
B
W
B
B
W
W
W
W
B
W
B
W
B
W
B
W
B
B
W
B
B
B
W
W
W...

output:

1218

result:

ok single line: '1218'

Test #4:

score: 0
Accepted
time: 17ms
memory: 4192kb

input:

5000 1 1
B
W
B
W
B
B
B
B
W
W
W
W
B
W
W
W
W
W
W
W
B
B
B
B
B
B
W
W
W
B
B
B
B
B
B
B
W
B
W
B
W
B
B
W
B
B
W
B
B
B
W
B
W
B
B
B
B
W
B
W
W
B
W
B
W
B
W
W
W
W
B
B
W
W
W
B
W
W
W
W
B
W
B
W
B
W
W
W
W
B
B
W
B
W
B
W
B
B
W
W
W
B
B
B
B
W
W
W
B
W
B
W
B
B
B
W
B
W
B
W
B
B
B
W
B
W
B
B
B
W
B
B
B
B
W
W
B
W
B
W
W
W
W
W
B
W...

output:

242900000

result:

ok single line: '242900000'

Test #5:

score: 0
Accepted
time: 2ms
memory: 4340kb

input:

1 5000 1
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...

output:

100000

result:

ok single line: '100000'

Test #6:

score: 0
Accepted
time: 89ms
memory: 4388kb

input:

2 2500 1
BWBBWWWBBBWBWBBBBBBBWBBBBBWWWWBBWBWWBBBBBBBBBWBWBWBBWWBBWWWBBWWWBBWWWWBWBBBWWBWBWBWWBBBWBWWWWWWWWWBBBBWWWBBBBWWBWBWBWBWBWWBWBBBBBBWBBWWWBWWBWWBWWBWWWBWWWBBBBBBBWBBWWBWWWWWWWBBBBWWBBBBBWWWBBBBBBWBWWWBWWWWBBBBWWWWWBWWBBBBWWWBWWBBWBWBBWWWBBBWWBBWBBWWBWWBBWBWBBWBWWWBWWWWWBBWWWBWWWWWWBWWWBBBWWBW...

output:

12335546

result:

ok single line: '12335546'

Test #7:

score: 0
Accepted
time: 97ms
memory: 4288kb

input:

1666 3 1
WBB
WWB
BWB
BWW
WWB
WWB
BBB
BBB
BBW
WBB
BBB
BBW
BWW
WWB
BBB
BBW
WWW
BBW
WWW
BWW
BWB
WWB
BWB
WWW
BWB
BWW
WWB
BWW
BWB
BBB
BBW
BBB
BWB
WWB
WBW
WWB
BWB
BWW
BWB
WWW
BBW
BBW
BBW
BWW
BWB
BBB
WWB
BBB
BBB
WBB
BBW
BBB
BBW
BBB
BBB
WBW
BBW
WBW
BBB
BWB
WBW
BBW
WWW
WWW
WWW
BWB
WWB
BBW
WBB
WWB
BWW
BBW
WBW...

output:

11971988

result:

ok single line: '11971988'

Test #8:

score: 0
Accepted
time: 91ms
memory: 4292kb

input:

4 1 1250
W
B
W
B
B
W
B
B
B
W
B
B
W
W
W
W
B
B
B
B
W
B
B
B
B
W
W
B
W
W
B
W
W
B
W
W
B
B
W
B
B
W
B
B
W
B
W
W
B
W
W
B
W
B
W
B
W
W
W
B
B
B
W
W
B
B
W
B
B
B
W
B
B
W
W
W
B
B
W
B
W
B
B
B
W
B
B
W
B
W
B
B
B
B
B
W
W
W
B
W
B
W
W
W
W
B
W
B
W
B
B
B
W
W
B
W
W
W
W
W
B
B
B
B
B
W
W
W
W
B
B
W
W
W
W
W
B
B
B
B
B
B
W
W
W
B...

output:

12131611

result:

ok single line: '12131611'

Test #9:

score: 0
Accepted
time: 26ms
memory: 4340kb

input:

70 71 1
WBBWBBBWWBBBWWWBBBWWBWWWBWBBBWBWWWWWBWWBBWBWWWBWBWWBBWWBBWWBBBWBWWWWWWB
WWBBBWWBWWBWBBWBBWWWWBBBWWWBBWWBBWWWWWBWWWBWWBWWBWBWWBBWWBBWBWWBWBWBBWW
BWWWBWBBBBWWWWWWBWWBBWWBWWWWWBWWWWBBWBBWBWBWWBWWBBBBWBBBBWBBWWWWBBBBWWB
BWBWBWBBWWWBBWWBBWWBWWBBWWBWBBWBWBBWBWWBWWBBBWBWWWBBWBBBWWWBBWBBBWWWBBW
WWWW...

output:

11904642

result:

ok single line: '11904642'

Test #10:

score: 0
Accepted
time: 55ms
memory: 4248kb

input:

12 4 95
BBWW
WBWW
BWBW
WWBW
BWBB
BWBW
WBWW
BWWB
WWBW
BWBW
WWWB
BWBW
WWWB
WBWB
BWBB
BBBW
WBBB
BWWW
BWWW
BBWW
WWBW
WBWB
WWBB
WWWW
WBWW
BBBW
WBBB
WWWW
WBBW
BBBB
WWBB
WBWW
WWWW
BBWW
WBBW
WWBW
WWWB
WWWB
BWWW
BWWW
BWWB
BWBW
BBBB
WWWB
WBBB
WWWB
WWWW
WBWB
WWWB
BBBB
WWBB
WBBW
BBWB
BBWB
WWWW
WWBW
WBWW
WBWW
WW...

output:

10402

result:

ok single line: '10402'

Test #11:

score: 0
Accepted
time: 17ms
memory: 4640kb

input:

25 10 20
BBWBWBWBBW
BBBWBBWBWW
WBWBWBWWWB
WBWBBWBWBW
WWWWWWWBWB
BBWBWBWWBB
BBBBBWBWWB
BWWWWBWWBW
BWBBBBWWWW
WWBBWBWBWW
WWBWWWBBWW
BWBWWBBWBB
BBWBBWBWWB
WBBBBBWWWW
BBWWBBBWWB
WWWWBWWWWB
WBBBWWBWBW
WBBWBWWBBB
BBWBWWBBWW
WWBWBWBWWB
BBBBWWBWBB
WWWWWWBBWB
WWWBWWBBBW
WBBWWWWBWW
BBBWWWBWWB
BWWWBWBBBB
BBBWW...

output:

11106

result:

ok single line: '11106'

Test #12:

score: 0
Accepted
time: 33ms
memory: 4236kb

input:

50 2 50
BB
WB
BB
BB
BB
BW
BW
WW
BB
WB
WW
BW
WB
BB
BW
WW
BW
BW
BB
WB
WB
BW
WB
WB
WW
WW
WB
BB
WW
BW
WB
BW
WW
BB
BW
BB
BW
BB
WB
WW
WW
WW
BB
WW
BW
BB
BB
BB
BB
WB
BW
WW
WB
BW
BW
BW
WW
WB
BB
WW
WW
BB
WW
BB
WB
BB
BW
BB
BB
WB
WW
BB
WW
WB
WB
WW
WW
BB
BW
WB
WB
WW
WB
WB
WB
WB
BB
WB
WW
BW
WW
BB
WB
BW
BW
WB
WB
W...

output:

11686

result:

ok single line: '11686'

Test #13:

score: 0
Accepted
time: 68ms
memory: 4308kb

input:

4 5 210
BWBWW
BBBWW
WBWWW
WBWWW
WBWBB
BWBWW
BBBWB
WBBWB
BWWWB
BWBBB
BWBBB
WBBBB
BBBBB
WWBWB
WBBBW
WBWWB
WBBBB
BBWBB
BWWBB
WBBWW
WWWBW
WBBBW
WWBBB
WWBBB
WWBWB
BWBWW
BWBBB
BWWBB
BBWBB
BWWWB
WWBBW
WBBBB
WBWBW
BBWBW
WBBBB
BWBWW
BBBWW
BBWWW
WWBBB
WWWWB
WWWBB
BBBWB
WWBWB
BBWBW
BBBBB
BBBBB
WWWWW
BBWBB
WWBW...

output:

9895

result:

ok single line: '9895'

Test #14:

score: 0
Accepted
time: 18ms
memory: 4364kb

input:

15 43 7
BWWWWBWBWBBBWWWWWBWBWBBBBBWWBBBBWWBWBWWBWBW
BBWBWBWBBBWBBWWWWBWWWWWWBBBBBWWBWBWWWBBBWWB
BWBBWBBBBBWBBWBBBWBBBBBBBWBBBBBWWWWBBBBBBBW
BWBWWBBWBWBBBBWBBWBWWWWWWWBBWBWWBWBBWBBWBBB
BBWWWBWWWBWWBWWBBWWWWWWWWBBWWWWWWBWBBBWWWBB
WBWWBWBWBWWBWWWWWWWWBWWWBWWWWWBWWBBWBBBBWBW
BBBBWWWBBWBBBBBBWWWBWBWWBBWW...

output:

10218

result:

ok single line: '10218'

Test #15:

score: 0
Accepted
time: 54ms
memory: 4444kb

input:

10 10 50
BBBBWWBBWW
BWBBWBWWBB
WWBBWWWWBB
WBWWBBWWBW
WBWBWBWBWW
BBWBWWBWBB
BWBWBBWBBB
WWWBWBBBBW
WBWWBBWWBW
BWWWWBBWBB
WWWWBWWWBW
BBWBWWWBWB
WWWWWWWBBB
WBBBWWWWBB
WWWBWBBBBW
BWWWBWWWBB
WWBBBBBBWB
BWBBWBWWWB
BBWWWWWWWB
WWBWWBBWWW
BWWWBWWBBB
WWBBWWWBBB
WWWBWWBWWW
BWBWWBBWBW
BBBBBWBWBW
WBWWWWWBBB
BBBBB...

output:

113532736

result:

ok single line: '113532736'

Test #16:

score: 0
Accepted
time: 19ms
memory: 4668kb

input:

16 17 18
WBWBWBWBWWWWBBWBB
BBWBBWWWWBWBWBBBW
BBWBWBBBBBWBWWBWB
WBBBBBWWBBBBBWWBB
WBBWWWWBWBWBWWWBW
WBBWWWWWWBWWBWWBW
WWBBBBBBBWWBBWBWB
WWBWBWWWBWWWWBWBW
BBBBBBBBBBWWWBBBW
WWBBWBWBBWBBWBWWW
WBBWBBBBBBWWWWWBW
BBBBWWBBWBBBBBBBB
WBWWBWWWBBWWWBWBW
WBBWBBBBWBWBWBBWB
WBBBWBWBWBBBWWWWB
WWBWBWWWWBWWBWBWB
WWB...

output:

109472675

result:

ok single line: '109472675'

Test #17:

score: 0
Accepted
time: 3ms
memory: 4660kb

input:

17 17 17
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBB
BBB...

output:

100000

result:

ok single line: '100000'

Test #18:

score: 0
Accepted
time: 7ms
memory: 4444kb

input:

17 17 17
WWWBBBBWWBBBWWBWW
WWWWBBBBBWBBBBBWW
BWWWBBWWBWBWBWWWW
WBBBBWBWWBWBWWWWB
BWWBWWWWWBWBBBBWW
WBBBWWBBBBWBBBWWB
BWWWBBBBWWBWBWBWW
WWBWBWBBBBWBWBBBW
WWBWWWBWBBWBWWWBW
BWWBBWWBBBWBWBWWB
BBBWBBBWWBWBWBWWB
WWWBWWWBBWBBWWWBB
WBBBWBWBBBWWWBBBW
WBWBWBBBWBWBBWWWW
BBBWWBWWBWWBWBBBB
WBBBWBBWBBWBBBWBB
WWW...

output:

1128

result:

ok single line: '1128'

Test #19:

score: 0
Accepted
time: 13ms
memory: 4464kb

input:

17 17 17
WWWBBWWBBWBWWBWWB
BWWBBBWWWWWWWBWBB
WWWBWBBBBBWWWWWBB
WWWWWWBWBBBBWWWBW
WBWWBBWWWBBWBWWWB
BWBBWWWBBWWWBBBBW
WBBBBWBWWWBWWWBBB
WWWWWWWWBBWWWWWBW
WWWWBBWBWWWWWBWWB
BBBBBBWWBBBWBBBWW
BBBBBBBBBWWWWWWWB
BBWWWWBBWWBBWWBBB
WBWBBBBWWBWBBWWBB
BBBBWBWWWBBBBBBWB
BWBWWWBBWWBBWBWBB
BBWWWBWWBWBWWBWBB
WBB...

output:

5346

result:

ok single line: '5346'

Test #20:

score: 0
Accepted
time: 25ms
memory: 4448kb

input:

17 17 17
WWBBWWWWWBWWWBBBW
BWWWWWWBWBWWBBWWW
WWWWWBWBWBWWWWWBW
WWWWBWBBBBWBWWWWW
BBBBWBBWWWWWBWWWW
WBWWBWWWBBBBBWBBW
BBWWWWWBWBBBBWBBW
BWWBBBWBWWWBBWWBW
WWBBWWWBBWWBBWBWB
WBBBWBWBBBBBBBBWW
BWWBWBBWBWWBWBBBB
WWWBWWWWWBWBBWWWW
BBBBBBWBWWWBWBBBB
WWWWWBBBBBBWWWWWB
BWBBWWWBWBBWWBBWB
WBWBBBBBWBWBWWBBB
WWW...

output:

113499454

result:

ok single line: '113499454'

Extra Test:

score: 0
Extra Test Passed