# Japan Alumni Group Summer Camp 2013 Warming Up

## Submission #102014

### Source codeソースコード

```#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

Task問題 C - Containers あずにゃん vs. binding.pry 2013/09/21 04:05:45 +0000 C++11 (GCC 4.8.1) AC 100 5450 Byte 31 ms 1056 KB

### Test case

#### Set

Set name Score得点 / Max score Cases
All 100 / 100 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

#### Test case

 Case name Status状態 Exec time実行時間 Memory usageメモリ使用量 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