Submission #3644698


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back

struct edge{ int to,cap,rev; };

const int MAX_V = 222;
const int F_INF = 19191919;
vector<edge> G[MAX_V];
int level[MAX_V], iter[MAX_V];

void add_edge(int from, int to, int cap){
    G[from].pb({to,cap,(int)G[to].size()});
    G[to].pb({from,0,(int)G[from].size()-1});
}

void dinic_bfs(int s){
    memset(level,-1,sizeof(level));
    queue<int> que;
    level[s] = 0;
    que.push(s);
    while(!que.empty()){
        int v = que.front();
        que.pop();
        rep(i,G[v].size()){
            edge &e = G[v][i];
            if(e.cap>0 & level[e.to]<0){
                level[e.to] = level[v]+1;
                que.push(e.to);
            }
        }
    }
}

int dinic_dfs(int v, int t, int f){
    if(v==t) return f;
    for(int &i=iter[v]; i<(int)G[v].size(); ++i){
        edge &e = G[v][i];
        if(e.cap>0 && level[v]<level[e.to]){
            int d = dinic_dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(int s, int t){
    int flow = 0;
    while(1){
        dinic_bfs(s);
        if(level[t]<0) return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while( (f=dinic_dfs(s,t,F_INF)) > 0 ) flow += f;
    }
}

int solve(){
    int h,w;
    cin >>h >>w;

    int one = 0;
    vector<vector<int>> u(h,vector<int>(w));
    rep(i,h)rep(j,w){
        cin >>u[i][j];
        one += u[i][j];
    }

    vector<int> f(w),s(h);
    rep(i,w) cin >>f[i];
    rep(i,h) cin >>s[i];

    rep(i,h)rep(j,w){
        if(u[i][j]==1) {
            if(min(f[j],s[i]) == 0) return -1;
        }
    }

    rep(i,h){
        int tmp = 0;
        rep(j,w)if(u[i][j]) tmp = max(tmp, min(s[i],f[j]));
        if(tmp < s[i]) return -1;
    }

    rep(i,w){
        int tmp = 0;
        rep(j,h)if(u[j][i]) tmp = max(tmp, min(f[i],s[j]));
        if(tmp < f[i]) return -1;
    }

    int ans = 0;
    for(int ww=100; ww>=2; --ww){
        //printf(" ww %d\n", ww);
        rep(i,MAX_V) G[i].clear();

        int S = h+w, T = S+1;
        rep(i,h) add_edge(S,i,1);
        rep(i,w) add_edge(h+i,T,1);

        rep(i,h)rep(j,w)if(u[i][j] && s[i]==ww && f[j]==ww){
//            printf(" ww %d:: %d -> %d\n",ww,i,j);
            add_edge(i,h+j,1);
        }

        int ff = max_flow(S,T);
//        printf(" ff %d\n", ff);

        int ct = 0;
        rep(i,h) ct += (s[i]==ww);
        rep(i,w) ct += (f[i]==ww);

        ans += (ww-1)*(ct-ff);
    }
    ans += one;

    return ans;
}

int main(){
    cout << solve() << endl;
    return 0;
}

Submission Info

Submission Time
Task C - Containers
User WAsedAC1
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2913 Byte
Status AC
Exec Time 9 ms
Memory 384 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 1 ms 256 KB
10 AC 1 ms 256 KB
11 AC 1 ms 256 KB
12 AC 1 ms 256 KB
13 AC 1 ms 256 KB
14 AC 1 ms 256 KB
15 AC 1 ms 256 KB
16 AC 1 ms 256 KB
17 AC 1 ms 256 KB
18 AC 1 ms 256 KB
19 AC 1 ms 256 KB
2 AC 1 ms 256 KB
20 AC 6 ms 256 KB
21 AC 6 ms 384 KB
22 AC 8 ms 384 KB
23 AC 3 ms 256 KB
24 AC 9 ms 384 KB
25 AC 3 ms 256 KB
26 AC 8 ms 384 KB
27 AC 3 ms 256 KB
28 AC 6 ms 384 KB
29 AC 3 ms 256 KB
3 AC 1 ms 256 KB
30 AC 2 ms 256 KB
31 AC 2 ms 256 KB
32 AC 3 ms 256 KB
33 AC 2 ms 256 KB
34 AC 3 ms 256 KB
35 AC 2 ms 256 KB
36 AC 3 ms 256 KB
37 AC 2 ms 256 KB
38 AC 3 ms 256 KB
39 AC 2 ms 256 KB
4 AC 1 ms 256 KB
40 AC 2 ms 256 KB
41 AC 2 ms 256 KB
42 AC 2 ms 256 KB
43 AC 2 ms 256 KB
44 AC 2 ms 256 KB
45 AC 2 ms 256 KB
46 AC 2 ms 256 KB
47 AC 2 ms 256 KB
48 AC 2 ms 256 KB
49 AC 2 ms 256 KB
5 AC 1 ms 256 KB
6 AC 2 ms 256 KB
7 AC 2 ms 256 KB
8 AC 2 ms 256 KB
9 AC 1 ms 256 KB