QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #83252 | #1197. Draw in Straight Lines | maoyiting | TL | 2ms | 3804kb | C++14 | 1.5kb | 2023-03-01 09:54:35 | 2023-03-01 09:54:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=6510,M=2.1e4+5;
int n,m,a,b,C,b1[N][N],b2[N][N],w1[N][N],w2[N][N],s,t,tot,cnt=1,hd[N],cur[N],to[M],nxt[M],c[M],d[N],ans;
char o[N];
queue<int>q;
void add(int x,int y,int z){
to[++cnt]=y,nxt[cnt]=hd[x],hd[x]=cnt,c[cnt]=z;
to[++cnt]=x,nxt[cnt]=hd[y],hd[y]=cnt,c[cnt]=0;
}
bool bfs(){
fill(d,d+1+tot,-1),q.push(s),d[s]=0,cur[s]=hd[s];
while(q.size()){
int x=q.front(),y;q.pop();
for(int i=hd[x];i;i=nxt[i])
if(!~d[y=to[i]]&&c[i]) d[y]=d[x]+1,cur[y]=hd[y],q.push(y);
}
return ~d[t];
}
int dfs(int x,int f){
if(x==t) return f;
int ans=0,v;
for(int &i=cur[x],y;i;i=nxt[i])
if(d[y=to[i]]==d[x]+1&&c[i]){
c[i]-=(v=dfs(y,min(f,c[i]))),c[i^1]+=v,f-=v,ans+=v;
if(!f) break;
}
return ans;
}
signed main(){
scanf("%d%d%d%d%d",&n,&m,&a,&b,&C),t=++tot;
for(int i=1;i<=n;i++){
scanf("%s",o+1);
for(int j=1;j<=m;j++){
add(s,b1[i][j]=++tot,a+b*(j==1));
add(b2[i][j]=++tot,t,a+b*(i==1));
add(w1[i][j]=++tot,t,a+b*(j==1));
add(s,w2[i][j]=++tot,a+b*(i==1));
add(w1[i][j],b1[i][j],1e9),add(b2[i][j],w2[i][j],1e9);
if(o[j]=='#')
add(w1[i][j],t,1e9),add(s,w2[i][j],1e9),add(b1[i][j],b2[i][j],C);
else
add(b2[i][j],b1[i][j],1e9),add(w2[i][j],b1[i][j],C),add(b2[i][j],w1[i][j],C);
if(j>1) add(b1[i][j-1],b1[i][j],b),add(w1[i][j],w1[i][j-1],b);
if(i>1) add(b2[i][j],b2[i-1][j],b),add(w2[i-1][j],w2[i][j],b);
}
}
while(bfs()) ans+=dfs(s,1e9);
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3756kb
input:
3 3 1 2 3 .#. ### .#.
output:
10
result:
ok answer is '10'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3744kb
input:
2 7 0 1 1 ###.### ###.###
output:
3
result:
ok answer is '3'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3676kb
input:
5 5 1 4 4 ..#.. ..#.. ##.## ..#.. ..#..
output:
24
result:
ok answer is '24'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
7 24 1 10 10 ###...###..#####....###. .#...#...#.#....#..#...# .#..#......#....#.#..... .#..#......#####..#..... .#..#......#......#..... .#...#...#.#.......#...# ###...###..#........###.
output:
256
result:
ok answer is '256'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
5 5 0 3 2 ..#.. ..#.. ##.## ..#.. ..#..
output:
11
result:
ok answer is '11'
Test #6:
score: -100
Time Limit Exceeded
input:
40 40 40 40 40 ######################################## ######################################## ######################################## ######################################## ######################################## ######################################## #######################################...