Submission #101979


Source Code Expand

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define mp make_pair
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> Q;
typedef long long ll;

const int MX = 105, n20 = 1<<20;

int n, m;
int a[MX][MX];
int b[MX], c[MX];
int g[MX][MX], p[MX];
bool used[MX];
vector<int> x, y;

bool dfs(int v){
    used[v] = true;
    rep(i,y.size()){
        if(g[v][i] == 0) continue;
        int w = p[i];
        if(w == -1 || !used[w] && dfs(w)){
            p[i] = v;
            return true;
        }
    }
    return false;
}

int mch(){
    rep(i,x.size()){
        rep(j,y.size()){
            g[i][j] = a[x[i]][y[j]]&1;
        }
    }
    
    rep(i,x.size()){
        bool ok = false;
        rep(j,m) if(c[j] >= b[x[i]] && a[x[i]][j]) ok = true;
        if(!ok) return -1;
    }
    rep(i,y.size()){
        bool ok = false;
        rep(j,n) if(b[j] >= c[y[i]] && a[j][y[i]]) ok = true;
        if(!ok) return -1;
    }
    
    rep(i,y.size()) p[i] = -1;
    int res = 0;
    rep(i,x.size()){
        rep(j,x.size()) used[j] = false;
        if(dfs(i)) res++;
    }
    
    return res;
}

int main(){
	cin >> n >> m;
    int ans = 0;
	rep(i,n)rep(j,m){
        cin >> a[i][j];
        if(a[i][j]) ans++;
    }
    rep(j,m) cin >> c[j];
    rep(i,n) cin >> b[i];
    
    bool ok = true;
    rep(i,n){
        if(b[i] != 0) continue;
        int cnt = 0;
        rep(j,m) cnt += a[i][j];
        if(cnt) ok = false;
    }
    rep(j,m){
        if(c[j] != 0) continue;
        int cnt = 0;
        rep(i,n) cnt += a[i][j];
        if(cnt) ok = false;
    }
    
    for(int h = 100; h >= 1; h--){
        x.clear(); y.clear();
        rep(i,n) if(b[i] == h) x.push_back(i);
        rep(i,m) if(c[i] == h) y.push_back(i);
        
        int res = mch();
        if(res == -1){
            ok = false;
        }
        ans += (h-1)*(x.size()+y.size()-res);
    }
    
    if(ok) cout << ans << endl; else cout << -1 << endl;
	
	return 0;
}

Submission Info

Submission Time
Task C - Containers
User nikyaudo
Language C++ (G++ 4.6.4)
Score 100
Code Size 2185 Byte
Status AC
Exec Time 26 ms
Memory 936 KB

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 21 ms 804 KB
10 AC 21 ms 804 KB
11 AC 21 ms 800 KB
12 AC 20 ms 804 KB
13 AC 23 ms 804 KB
14 AC 23 ms 796 KB
15 AC 21 ms 800 KB
16 AC 20 ms 804 KB
17 AC 20 ms 804 KB
18 AC 21 ms 748 KB
19 AC 20 ms 924 KB
2 AC 21 ms 804 KB
20 AC 23 ms 800 KB
21 AC 25 ms 800 KB
22 AC 24 ms 808 KB
23 AC 24 ms 928 KB
24 AC 24 ms 848 KB
25 AC 26 ms 804 KB
26 AC 26 ms 928 KB
27 AC 25 ms 804 KB
28 AC 24 ms 804 KB
29 AC 24 ms 804 KB
3 AC 21 ms 936 KB
30 AC 22 ms 924 KB
31 AC 23 ms 804 KB
32 AC 22 ms 804 KB
33 AC 24 ms 804 KB
34 AC 22 ms 804 KB
35 AC 22 ms 804 KB
36 AC 22 ms 928 KB
37 AC 23 ms 804 KB
38 AC 23 ms 932 KB
39 AC 23 ms 808 KB
4 AC 21 ms 808 KB
40 AC 21 ms 928 KB
41 AC 22 ms 932 KB
42 AC 23 ms 808 KB
43 AC 20 ms 800 KB
44 AC 21 ms 796 KB
45 AC 21 ms 768 KB
46 AC 21 ms 808 KB
47 AC 22 ms 800 KB
48 AC 21 ms 804 KB
49 AC 22 ms 808 KB
5 AC 20 ms 800 KB
6 AC 22 ms 808 KB
7 AC 21 ms 920 KB
8 AC 22 ms 932 KB
9 AC 20 ms 800 KB