Submission #101925
Source Code Expand
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long ll;
const int INF = 1000000000;
const int MOD = 1000000007;
const double EPS = 1e-8;
typedef vector<vector<int> > Mat;
Mat G;
int H, W, U[110][110], F[110], S[110];
int hi[110][110], H_check[110], W_check[110];
int match[300];
bool use[300];
int dfs(int v) {
use[v] = true;
for (int i=0; i<int(G[v].size()); i++) {
int u=G[v][i], w=match[u];
if (w<0 || (!use[w] && dfs(w))) {
match[v]=u;
match[u]=v;
return true;
}
}
return false;
}
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);
int F_ma=0, S_ma=0;
for (int i=0; i<W; i++) F_ma = max(F_ma, F[i]);
for (int i=0; i<H; i++) S_ma = max(S_ma, S[i]);
bool bad = false;
for (int i=0; i<H; i++) {
for (int j=0; j<W; j++) {
if (U[i][j]) hi[i][j] = min(S[i], F[j]);
}
}
for (int i=0; i<H; i++) {
for (int j=0; j<W; j++) {
if (U[i][j] && hi[i][j]==0) bad = true;
}
}
for (int i=0; i<H; i++) {
bool ok=false;
for (int j=0; j<W; j++) if (hi[i][j]==S[i]) ok=true;
if (!ok) bad=true;
}
for (int j=0; j<W; j++) {
bool ok=false;
for (int i=0; i<H; i++) if(hi[i][j]==F[j]) ok=true;
if(!ok) bad=true;
}
memset(hi, 0, sizeof hi);
if (bad || F_ma != S_ma) {
puts("-1");
return 0;
}
G = Mat(H+W);
for (int i=0; i<H; i++) {
for (int j=0; j<W; j++) {
if (S[i] == F[j] && U[i][j]) {
G[i].push_back(H+j);
G[H+j].push_back(i);
}
}
}
memset(match, -1, sizeof match);
for (int i=0; i<H; i++) {
if (match[i] < 0) {
memset(use, 0, sizeof use);
dfs(i);
}
}
for (int i=0; i<H; i++) {
if (match[i]>=0) {
int j = match[i]-H;
//printf("%d %d\n", i, j);
hi[i][j] = S[i];
H_check[i] = S[i];
W_check[j] = S[i];
}
}
vector<pair<int, int> > v;
for (int i=0; i<H; i++) {
if (S[i] > H_check[i]) v.push_back(make_pair(S[i], i));
}
for (int j=0; j<W; j++) {
if (F[j] > W_check[j]) v.push_back(make_pair(F[j], j+H));
}
sort(v.rbegin(), v.rend());
for (int t=0; t<v.size(); t++) {
if (v[t].second >= H) {
int j=v[t].second - H;
for (int i=0; i<H; i++) {
if (H_check[i] >= v[t].first && U[i][j] && hi[i][j] == 0) {
hi[i][j] = W_check[j] = v[t].first;
break;
}
}
} else {
int i=v[t].second;
for (int j=0; j<W; j++) {
if (W_check[j] >= v[t].first && U[i][j] && hi[i][j] == 0) {
hi[i][j] = H_check[i] = v[t].first;
break;
}
}
}
}
for (int i=0; i<H; i++) {
for (int j=0; j<W; j++) {
if (U[i][j] && hi[i][j]==0) {
hi[i][j] = 1;
}
}
}
int ans=0;;
for (int i=0; i<H; i++) {
for (int j=0; j<W; j++) {
ans += hi[i][j];
}
}
for (int i=0; i<H; i++) {
for (int j=0; j<W; j++) {
//printf("%d ", hi[i][j]);
}
//puts("");
}
//for (int i=0; i<H; i++) printf("%d ", match[i]-H); puts("");
//for (int i=0; i<W; i++) printf("%d ", match[i+H]); puts("");
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Containers |
User |
YellowYell |
Language |
C++11 (GCC 4.8.1) |
Score |
100 |
Code Size |
3978 Byte |
Status |
AC |
Exec Time |
30 ms |
Memory |
1056 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:33:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &H, &W);
^
./Main.cpp:35:56: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for (int j=0; j<W; j++) scanf("%d", &(U[i][j]));
^
./Main.cpp:37:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for (int i=0; i<W; i++) scanf("%d", F+i);
^
./Main.cpp:38:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for (int i=0; i<H; i++) scanf("%d", S+i);
^
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 |
20 ms |
932 KB |
10 |
AC |
22 ms |
808 KB |
11 |
AC |
21 ms |
928 KB |
12 |
AC |
21 ms |
936 KB |
13 |
AC |
21 ms |
812 KB |
14 |
AC |
21 ms |
928 KB |
15 |
AC |
20 ms |
804 KB |
16 |
AC |
20 ms |
800 KB |
17 |
AC |
21 ms |
804 KB |
18 |
AC |
22 ms |
804 KB |
19 |
AC |
23 ms |
804 KB |
2 |
AC |
30 ms |
844 KB |
20 |
AC |
23 ms |
804 KB |
21 |
AC |
24 ms |
928 KB |
22 |
AC |
23 ms |
932 KB |
23 |
AC |
21 ms |
804 KB |
24 |
AC |
23 ms |
808 KB |
25 |
AC |
21 ms |
796 KB |
26 |
AC |
22 ms |
932 KB |
27 |
AC |
23 ms |
872 KB |
28 |
AC |
22 ms |
1056 KB |
29 |
AC |
23 ms |
936 KB |
3 |
AC |
21 ms |
804 KB |
30 |
AC |
21 ms |
924 KB |
31 |
AC |
21 ms |
800 KB |
32 |
AC |
22 ms |
932 KB |
33 |
AC |
21 ms |
784 KB |
34 |
AC |
23 ms |
928 KB |
35 |
AC |
20 ms |
804 KB |
36 |
AC |
20 ms |
800 KB |
37 |
AC |
21 ms |
804 KB |
38 |
AC |
22 ms |
868 KB |
39 |
AC |
21 ms |
804 KB |
4 |
AC |
21 ms |
804 KB |
40 |
AC |
21 ms |
932 KB |
41 |
AC |
20 ms |
804 KB |
42 |
AC |
22 ms |
800 KB |
43 |
AC |
21 ms |
808 KB |
44 |
AC |
22 ms |
808 KB |
45 |
AC |
23 ms |
796 KB |
46 |
AC |
22 ms |
860 KB |
47 |
AC |
21 ms |
804 KB |
48 |
AC |
21 ms |
800 KB |
49 |
AC |
21 ms |
924 KB |
5 |
AC |
21 ms |
788 KB |
6 |
AC |
22 ms |
864 KB |
7 |
AC |
21 ms |
924 KB |
8 |
AC |
21 ms |
804 KB |
9 |
AC |
22 ms |
920 KB |