Submission #478185
Source Code Expand
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#define SIZE 210
#define INF 1000000000
using namespace std;
struct MaxFlow
{
struct edge
{
int to,cap,rev;
edge(int t,int c,int r)
{
to=t;
cap=c;
rev=r;
}
};
vector <edge> vec[SIZE];
bool use[SIZE];
void init()
{
for(int i=0;i<SIZE;i++)
{
vec[i].clear();
}
}
void add(int start,int end,int cap)
{
int s=vec[start].size(),e=vec[end].size();
vec[start].push_back(edge(end,cap,e));
vec[end].push_back(edge(start,0,s));
}
int dfs(int v,int t,int f)
{
if(v==t) return f;
use[v]=true;
for(int i=0;i<vec[v].size();i++)
{
edge &e=vec[v][i];
if(!use[e.to]&&e.cap>0)
{
int d=dfs(e.to,t,min(f,e.cap));
if(d>0)
{
e.cap-=d;
vec[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int max_flow(int s,int t)
{
int flow=0;
while(1)
{
memset(use,false,sizeof(use));
int f=dfs(s,t,INF);
if(f==0) return flow;
flow+=f;
}
}
};
MaxFlow solve;
int mp[SIZE][SIZE];
int f[SIZE],s[SIZE];
int main()
{
int h,w;
scanf("%d %d",&h,&w);
for(int i=0;i<h;i++)
{
for(int j=0;j<w;j++)
{
scanf("%d",&mp[i][j]);
}
}
for(int i=0;i<w;i++) scanf("%d",&f[i]);
for(int i=0;i<h;i++) scanf("%d",&s[i]);
int ret=0;
for(int i=0;i<w;i++) ret+=max(f[i]-1,0);
for(int i=0;i<h;i++) ret+=max(s[i]-1,0);
for(int i=0;i<h;i++)
{
for(int j=0;j<w;j++)
{
ret+=mp[i][j];
if(mp[i][j]==1&&(f[i]==0||s[i]==0))
{
puts("-1");
return 0;
}
}
}
for(int k=SIZE;k>=1;k--)
{
vector <int> vw,vh;
for(int i=0;i<w;i++) if(f[i]==k) vw.push_back(i);
for(int i=0;i<h;i++) if(s[i]==k) vh.push_back(i);
if(vw.empty()&&vh.empty()) continue;
int S=vw.size()+vh.size(),T=S+1;
solve.init();
for(int i=0;i<vh.size();i++)
{
for(int j=0;j<vw.size();j++)
{
int x=vh[i],y=vw[j];
if(mp[x][y]==1)
{
solve.add(i,j+vh.size(),1);
}
}
}
for(int i=0;i<vh.size();i++)
{
int x=vh[i];
bool up=false;
for(int j=0;j<w;j++)
{
if(f[j]>=k&&mp[x][j]==1)
{
up=true;
break;
}
}
if(!up)
{
puts("-1");
return 0;
}
}
for(int i=0;i<vw.size();i++)
{
int y=vw[i];
bool up=false;
for(int j=0;j<h;j++)
{
if(s[j]>=k&&mp[j][y]==1)
{
up=true;
break;
}
}
if(!up)
{
puts("-1");
return 0;
}
}
for(int i=0;i<vh.size();i++) solve.add(S,i,1);
for(int i=0;i<vw.size();i++) solve.add(i+vh.size(),T,1);
int gt=solve.max_flow(S,T);
ret-=gt*(k-1);
}
printf("%d\n",ret);
return 0;
}
Submission Info
Submission Time
2015-08-27 23:42:07+0900
Task
C - Containers
User
yutaka1999
Language
C++ (GCC 4.4.7)
Score
0
Code Size
2791 Byte
Status
WA
Exec Time
30 ms
Memory
1056 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:79: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:84: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:87: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:88: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
Judge Result
Set Name
All
Score / Max Score
0 / 100
Status
Set Name
Test Cases
All
1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 4, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 5, 6, 7, 8, 9
Case Name
Status
Exec Time
Memory
1
AC
27 ms
872 KB
10
AC
26 ms
924 KB
11
AC
25 ms
924 KB
12
WA
26 ms
928 KB
13
WA
25 ms
928 KB
14
WA
26 ms
800 KB
15
AC
25 ms
928 KB
16
WA
25 ms
924 KB
17
WA
26 ms
924 KB
18
AC
26 ms
880 KB
19
AC
26 ms
880 KB
2
AC
26 ms
880 KB
20
AC
27 ms
920 KB
21
AC
27 ms
928 KB
22
AC
27 ms
928 KB
23
AC
28 ms
928 KB
24
AC
29 ms
876 KB
25
AC
27 ms
932 KB
26
AC
28 ms
1056 KB
27
AC
28 ms
920 KB
28
AC
29 ms
1004 KB
29
AC
27 ms
924 KB
3
AC
24 ms
804 KB
30
WA
26 ms
928 KB
31
AC
26 ms
928 KB
32
AC
25 ms
928 KB
33
AC
26 ms
928 KB
34
AC
24 ms
880 KB
35
AC
26 ms
872 KB
36
WA
30 ms
872 KB
37
AC
26 ms
928 KB
38
AC
27 ms
868 KB
39
AC
28 ms
872 KB
4
AC
26 ms
808 KB
40
WA
26 ms
880 KB
41
AC
26 ms
920 KB
42
AC
26 ms
920 KB
43
AC
25 ms
928 KB
44
WA
29 ms
924 KB
45
WA
26 ms
880 KB
46
WA
25 ms
924 KB
47
WA
25 ms
920 KB
48
AC
26 ms
928 KB
49
AC
26 ms
868 KB
5
AC
26 ms
876 KB
6
AC
26 ms
924 KB
7
AC
26 ms
872 KB
8
AC
25 ms
928 KB
9
AC
26 ms
876 KB