Submission #478188
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[j]==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:45:25+0900
Task
C - Containers
User
yutaka1999
Language
C++ (GCC 4.4.7)
Score
100
Code Size
2791 Byte
Status
AC
Exec Time
32 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
100 / 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
32 ms
872 KB
10
AC
25 ms
928 KB
11
AC
26 ms
864 KB
12
AC
28 ms
872 KB
13
AC
28 ms
808 KB
14
AC
25 ms
924 KB
15
AC
25 ms
924 KB
16
AC
25 ms
924 KB
17
AC
26 ms
920 KB
18
AC
25 ms
928 KB
19
AC
24 ms
848 KB
2
AC
25 ms
928 KB
20
AC
25 ms
876 KB
21
AC
26 ms
880 KB
22
AC
27 ms
924 KB
23
AC
28 ms
944 KB
24
AC
30 ms
932 KB
25
AC
28 ms
868 KB
26
AC
28 ms
1056 KB
27
AC
27 ms
920 KB
28
AC
28 ms
1000 KB
29
AC
30 ms
876 KB
3
AC
25 ms
924 KB
30
AC
24 ms
804 KB
31
AC
26 ms
932 KB
32
AC
25 ms
928 KB
33
AC
26 ms
932 KB
34
AC
26 ms
876 KB
35
AC
25 ms
928 KB
36
AC
26 ms
920 KB
37
AC
24 ms
876 KB
38
AC
25 ms
924 KB
39
AC
26 ms
864 KB
4
AC
25 ms
920 KB
40
AC
23 ms
924 KB
41
AC
25 ms
928 KB
42
AC
25 ms
932 KB
43
AC
25 ms
928 KB
44
AC
25 ms
928 KB
45
AC
25 ms
924 KB
46
AC
25 ms
924 KB
47
AC
24 ms
928 KB
48
AC
24 ms
876 KB
49
AC
25 ms
932 KB
5
AC
25 ms
800 KB
6
AC
26 ms
928 KB
7
AC
25 ms
928 KB
8
AC
25 ms
932 KB
9
AC
25 ms
928 KB