Submission #101894
Source Code Expand
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int H, W;
int U[100][100], F[100], S[100];
int n0, n1, m, ptr[100], next[20000], zu[20000];
int to[100], fr[100], us[100], total;
int lev[100], que[100], *qb, *qe;
void init(int _n0, int _n1){
n0 = _n0; n1 = _n1; m = 0; memset(ptr, ~0, n0*4);
}
void ae(int u, int v){
next[m] = ptr[u];
ptr[u] = m;
zu[m] = v;
++m;
}
int augument(int u) {
int i, v, w;
us[u] = total;
for(i = ptr[u]; ~i; i = next[i]) {
if(!~(w = fr[v=zu[i]]) || us[w] != total && lev[u] < lev[w] && augument(w)){
to[u] = v; fr[v] = u; return 1;
}
}
return 0;
}
int solve()
{
int f, i, u, w;
memset(to, ~0, n0*4); memset(fr, ~0, n1*4); memset(us, ~0, n1*4);
for(total=0; ; total+=f){
qb = qe = que;
memset(lev, ~0, n0*4);
for(u=0; u<n0; ++u) if(!~to[u]) lev[*qe++ = u] = 0;
for(;qb!=qe;) for(i = ptr[u = *qb++]; ~i; i = next[i]){
if(~(w = fr[zu[i]]) && !~lev[w]) lev[*qe++ = w] = lev[u] + 1;
}
for(f=0, u=0; u<n0; ++u) if(!~to[u]) f += augument(u);
if(!f) return total;
}
return -1;
}
int solve(int h)
{
//takasa h ni tsuite toku
bool valid[100][100];
int vc = 0;
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
valid[i][j] = (U[i][j]==1);
if(F[j] < h || S[i] < h) valid[i][j] = 0;
if(F[j] > h && S[i] > h) valid[i][j] = 0;
if(valid[i][j]) ++vc;
}
}
int reqr = 0;
for(int i=0;i<H;i++) if(S[i]==h){
++reqr;
bool flg = false;
for(int j=0;j<W;j++) if(valid[i][j]) flg = true;
if(!flg) return -10000000;
}
for(int j=0;j<W;j++) if(F[j]==h){
++reqr;
bool flg = false;
for(int i=0;i<H;i++) if(valid[i][j]) flg = true;
if(!flg) return -10000000;
}
init(H, W);
for(int i=0;i<H;i++)
for(int j=0;j<W;j++) if(S[i]==h && F[j]==h && valid[i][j]) ae(i, j);
int tmp = reqr - solve();
return tmp * h + (vc - tmp);
}
int main()
{
scanf("%d%d", &H, &W);
for(int i=0;i<H;i++)
for(int j=0;j<W;j++) scanf("%d", &(U[i][j]));
for(int i=0;i<W;i++) scanf("%d", F+i);
for(int i=0;i<H;i++) scanf("%d", S+i);
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(S[i]==0 || F[j]==0){
if(U[i][j]==1){
puts("-1");
return 0;
}
}
}
}
int ret = 0;
for(int i=100;i>0;i--){
//printf("%d %d\n", i, solve(i));
ret += solve(i);
if(ret < 0){
puts("-1");
return 0;
}
}
printf("%d\n", ret);
return 0;
}
Submission Info
Submission Time
2013-09-21 11:34:05+0900
Task
C - Containers
User
Operasan
Language
C++ (GCC 4.4.7)
Score
100
Code Size
2480 Byte
Status
AC
Exec Time
29 ms
Memory
936 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:97: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:99: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:100: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:101: 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
19 ms
800 KB
10
AC
19 ms
676 KB
11
AC
21 ms
740 KB
12
AC
20 ms
928 KB
13
AC
20 ms
800 KB
14
AC
20 ms
804 KB
15
AC
21 ms
924 KB
16
AC
27 ms
808 KB
17
AC
21 ms
928 KB
18
AC
20 ms
800 KB
19
AC
20 ms
796 KB
2
AC
21 ms
804 KB
20
AC
27 ms
800 KB
21
AC
29 ms
796 KB
22
AC
26 ms
804 KB
23
AC
21 ms
800 KB
24
AC
25 ms
796 KB
25
AC
22 ms
928 KB
26
AC
27 ms
924 KB
27
AC
22 ms
808 KB
28
AC
28 ms
808 KB
29
AC
22 ms
736 KB
3
AC
21 ms
808 KB
30
AC
23 ms
936 KB
31
AC
21 ms
804 KB
32
AC
22 ms
808 KB
33
AC
21 ms
932 KB
34
AC
22 ms
936 KB
35
AC
21 ms
808 KB
36
AC
24 ms
784 KB
37
AC
21 ms
808 KB
38
AC
22 ms
932 KB
39
AC
20 ms
804 KB
4
AC
21 ms
808 KB
40
AC
21 ms
928 KB
41
AC
20 ms
792 KB
42
AC
22 ms
808 KB
43
AC
21 ms
804 KB
44
AC
21 ms
808 KB
45
AC
21 ms
804 KB
46
AC
21 ms
936 KB
47
AC
22 ms
932 KB
48
AC
22 ms
736 KB
49
AC
20 ms
804 KB
5
AC
21 ms
672 KB
6
AC
20 ms
804 KB
7
AC
21 ms
804 KB
8
AC
21 ms
932 KB
9
AC
21 ms
804 KB