Submission #102014
Source Code Expand
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int H, W;
bool check_consistency(const vector<vector<int> > &upper, const vector<int> &front, const vector<int> &side) {
vector<vector<int> > min_at(H, vector<int>(W, 0));
for(int r = 0; r < H; ++r) {
for(int c = 0; c < W; ++c) {
if(upper[r][c]) {
min_at[r][c] = min(front[c], side[r]);
if(min_at[r][c] == 0) return false;
}
}
}
// Check side
for(int r = 0; r < H; ++r) {
int max_val = 0;
for(int c = 0; c < W; ++c) {
if(upper[r][c]) max_val = max(max_val, min_at[r][c]);
}
if(max_val != side[r]) return false;
}
// Check front
for(int c = 0; c < W; ++c) {
int max_val = 0;
for(int r = 0; r < H; ++r) {
if(upper[r][c]) max_val = max(max_val, min_at[r][c]);
}
if(max_val != front[c]) return false;
}
return true;
}
/*
template <class Flow, class Cost>
struct edge
{
int index;
Flow capacity, flow;
Cost cost;
int back;
edge(int i, Flow c, Cost d, int b) : index(i), capacity(c), flow(0), cost(d), back(b) {}
};
template <class Flow, class Cost>
void make_edge(vector<edge<Flow, Cost> > *g, int src, int dst, Flow c, Cost d)
{
const int i = g[src].size(), j = g[dst].size();
g[src].push_back(edge<Flow, Cost>(dst, c, d, j));
g[dst].push_back(edge<Flow, Cost>(src, 0, -d, i));
}
template<class Flow, class Cost>
pair<Flow, Cost>
primal_dual(vector<edge<Flow, Cost> > *g, int N, int source, int sink, int max_flow)
{
pair<Flow, Cost> total;
static Cost h[MAXN], dist[MAXN];
static pair<int,int> parent[MAXN];
for(Flow f = max_flow; f > 0; ) {
fill_n(dist, N, 1000000);
dist[source] = 0;
fill_n(parent, N, make_pair(-1, -1));
}
}
*/
const int SIZE = 128;
const int INF = (int)1e9;
int hungarian(int N, int cost[SIZE][SIZE]) {
vector<int> xy(N, -1), yx(N, -1), lx(N, -INF), ly(N, 0);
for(int x = 0; x < N; ++x) {
for(int y = 0; y < N; ++y) {
lx[x] = max(lx[x], cost[x][y]);
}
}
for(int root = 0; root < N; ++root) {
vector<bool> left(N), right(N);
vector<int> slack(N), slackx(N, root), prev(N, -1);
left[root] = true;
for(int j = 0; j < N; ++j) {
slack[j] = lx[root] + ly[j] - cost[root][j];
}
while(true) {
int d = INF;
for(int i = 0; i < N; ++i) {
if(!right[i]) d = min(d, slack[i]);
}
for(int i = 0; i < N; ++i) {
if(left[i]) lx[i] -= d;
}
for(int i = 0; i < N; ++i) {
if(right[i]) ly[i] += d;
else slack[i] -= d;
}
for(int y = 0; y < N; ++y) {
if(!right[y] && slack[y] == 0) {
if(yx[y] >= 0) {
right[y] = true;
int a = yx[y];
if(!left[a]) {
left[a] = true;
prev[a] = slackx[y];
for(int j = 0; j < N; ++j) {
if(lx[a] + ly[j] - cost[a][j] < slack[j]) {
slack[j] = lx[a] + ly[j] - cost[a][j];
slackx[j] = a;
}
}
}
} else {
for(int cx = slackx[y], cy = y, ty; cx != -1; cx = prev[cx], cy = ty) {
ty = xy[cx];
yx[cy] = cx;
xy[cx] = cy;
}
goto NEXT;
}
}
}
}
NEXT:
;
}
int ret = 0;
for(int i = 0; i < N; ++i) {
ret += cost[i][xy[i]];
}
return ret;
}
int mat[SIZE][SIZE];
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
cin >> H >> W;
vector<vector<int> > upper(H, vector<int>(W, 0));
vector<int> front(W), side(H);
int acc = 0;
for(int r = 0; r < H; ++r) {
for(int c = 0; c < W; ++c) {
cin >> upper[r][c];
if(upper[r][c]) ++acc;
}
}
for(int x = 0; x < W; ++x) {
cin >> front[x];
if(front[x]) acc += front[x]-1;
}
for(int y = 0; y < H; ++y) {
cin >> side[y];
if(side[y]) acc += side[y]-1;
}
if(!check_consistency(upper, front, side)) {
cout << -1 << endl;
return 0;
}
fill_n((int*)mat, sizeof(mat)/sizeof(int), 0);
for(int r = 0; r < H; ++r) {
for(int c = 0; c < W; ++c) {
if(front[c] == side[r]) {
mat[r][c] = max(front[c], side[r]) - 1;
}
if(upper[r][c] == 0) {
mat[r][c] = 0;
}
}
}
/*
for(int r = 0; r < H; ++r) {
for(int c = 0; c < W; ++c) {
cout << mat[r][c] << ' ';
}
cout << endl;
}
*/
int res = hungarian(max(H, W), mat);
cout << acc - res << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Containers |
User |
binding_pry |
Language |
C++11 (GCC 4.8.1) |
Score |
100 |
Code Size |
5450 Byte |
Status |
AC |
Exec Time |
31 ms |
Memory |
1056 KB |
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 |
21 ms |
928 KB |
10 |
AC |
22 ms |
804 KB |
11 |
AC |
22 ms |
808 KB |
12 |
AC |
21 ms |
864 KB |
13 |
AC |
20 ms |
800 KB |
14 |
AC |
21 ms |
932 KB |
15 |
AC |
21 ms |
936 KB |
16 |
AC |
21 ms |
928 KB |
17 |
AC |
21 ms |
804 KB |
18 |
AC |
21 ms |
932 KB |
19 |
AC |
21 ms |
920 KB |
2 |
AC |
20 ms |
800 KB |
20 |
AC |
22 ms |
932 KB |
21 |
AC |
23 ms |
932 KB |
22 |
AC |
23 ms |
1056 KB |
23 |
AC |
23 ms |
932 KB |
24 |
AC |
23 ms |
920 KB |
25 |
AC |
22 ms |
808 KB |
26 |
AC |
23 ms |
932 KB |
27 |
AC |
22 ms |
928 KB |
28 |
AC |
23 ms |
928 KB |
29 |
AC |
22 ms |
800 KB |
3 |
AC |
21 ms |
800 KB |
30 |
AC |
21 ms |
800 KB |
31 |
AC |
22 ms |
800 KB |
32 |
AC |
24 ms |
792 KB |
33 |
AC |
22 ms |
808 KB |
34 |
AC |
20 ms |
800 KB |
35 |
AC |
21 ms |
748 KB |
36 |
AC |
21 ms |
928 KB |
37 |
AC |
21 ms |
928 KB |
38 |
AC |
21 ms |
796 KB |
39 |
AC |
21 ms |
796 KB |
4 |
AC |
21 ms |
804 KB |
40 |
AC |
21 ms |
932 KB |
41 |
AC |
21 ms |
804 KB |
42 |
AC |
27 ms |
800 KB |
43 |
AC |
22 ms |
804 KB |
44 |
AC |
22 ms |
804 KB |
45 |
AC |
21 ms |
800 KB |
46 |
AC |
22 ms |
928 KB |
47 |
AC |
21 ms |
804 KB |
48 |
AC |
20 ms |
932 KB |
49 |
AC |
23 ms |
928 KB |
5 |
AC |
21 ms |
796 KB |
6 |
AC |
31 ms |
860 KB |
7 |
AC |
20 ms |
924 KB |
8 |
AC |
21 ms |
864 KB |
9 |
AC |
23 ms |
804 KB |