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
AC × 49
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