Japan Alumni Group Summer Camp 2013 Warming Up

Submission #101925

Source codeソースコード

#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

Task問題 C - Containers
User nameユーザ名 最高にチキンです!
Created time投稿日時
Language言語 C++11 (GCC 4.8.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 3978 Byte
File nameファイル名
Exec time実行時間 30 ms
Memory usageメモリ使用量 1056 KB

Compiler messageコンパイルメッセージ

./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);
^

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