답안 #220632

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
220632	2020-04-08T10:16:15 Z	Vimmer	Skandi (COCI20_skandi)	C++14	55 / 110	4785 ms	11060 KB

skandi

#include <bits/stdc++.h>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 250005
#define MOD ll(998244353)

using namespace std;

typedef long long ll;

typedef long double ld;



int mt[N], idr[505][505];

vector <int> g[N];

bool mk[N];

bool kuna(int v)
{
    if (mk[v]) return 0;

    mk[v] = 1;

    for (auto it : g[v])
    {
        if (mt[it] == -1 || kuna(mt[it]))
            {
                mt[it] = v;

                return 1;
            }
    }

    return 0;
}
int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m;

    cin >> n >> m;

    string a[n];

    for (int i = 0; i < n; i++) cin >> a[i];

    int id = 0;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) idr[i][j] = id++;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
          if (a[i][j] == '0')
            {
                int x = i;

                while (a[x][j] == '0') x--;

                int y = j;

                while (a[i][y] == '0') y--;

                g[idr[x][j]].pb(idr[i][y]);
            }

    memset(mt, -1, sizeof(mt));

    for (int i = 0; i < N; i++)
    {
        if (sz(g[i]) == 0) continue;

        memset(mk, 0, sizeof(mk));

        kuna(i);
    }

    int ans = 0;

    for (int i = 0; i < N; i++) if (mt[i] != -1) ans++;

    cout << ans << endl;
}

Subtask #1

9.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	10 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
2	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
3	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
4	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
5	Partially correct	10 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
6	Partially correct	11 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
7	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
8	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
9	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
10	Partially correct	12 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
11	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
12	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
13	Partially correct	11 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
14	Partially correct	11 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
15	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
16	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
17	Partially correct	10 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
18	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
19	Partially correct	11 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
20	Partially correct	9 ms	7428 KB	First line is correct, but the reconstruction is not properly formatted.
21	Partially correct	11 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
22	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
23	Partially correct	11 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.

Subtask #2

16.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	10 ms	8320 KB	First line is correct, but the reconstruction is not properly formatted.
2	Partially correct	10 ms	7808 KB	First line is correct, but the reconstruction is not properly formatted.
3	Partially correct	12 ms	8192 KB	First line is correct, but the reconstruction is not properly formatted.
4	Partially correct	13 ms	7808 KB	First line is correct, but the reconstruction is not properly formatted.
5	Partially correct	11 ms	7784 KB	First line is correct, but the reconstruction is not properly formatted.
6	Partially correct	11 ms	7552 KB	First line is correct, but the reconstruction is not properly formatted.
7	Partially correct	12 ms	7552 KB	First line is correct, but the reconstruction is not properly formatted.
8	Partially correct	15 ms	7808 KB	First line is correct, but the reconstruction is not properly formatted.
9	Partially correct	11 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
10	Partially correct	20 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
11	Partially correct	18 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
12	Partially correct	17 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
13	Partially correct	19 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
14	Partially correct	27 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
15	Partially correct	25 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
16	Partially correct	26 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
17	Partially correct	23 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
18	Partially correct	16 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
19	Partially correct	18 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
20	Partially correct	15 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
21	Partially correct	18 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
22	Partially correct	18 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
23	Partially correct	17 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
24	Partially correct	13 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
25	Partially correct	20 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
26	Partially correct	23 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.

Subtask #3

30.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	10 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
2	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
3	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
4	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
5	Partially correct	10 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
6	Partially correct	11 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
7	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
8	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
9	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
10	Partially correct	12 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
11	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
12	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
13	Partially correct	11 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
14	Partially correct	11 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
15	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
16	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
17	Partially correct	10 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
18	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
19	Partially correct	11 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
20	Partially correct	9 ms	7428 KB	First line is correct, but the reconstruction is not properly formatted.
21	Partially correct	11 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
22	Partially correct	9 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
23	Partially correct	11 ms	7424 KB	First line is correct, but the reconstruction is not properly formatted.
24	Partially correct	10 ms	8320 KB	First line is correct, but the reconstruction is not properly formatted.
25	Partially correct	10 ms	7808 KB	First line is correct, but the reconstruction is not properly formatted.
26	Partially correct	12 ms	8192 KB	First line is correct, but the reconstruction is not properly formatted.
27	Partially correct	13 ms	7808 KB	First line is correct, but the reconstruction is not properly formatted.
28	Partially correct	11 ms	7784 KB	First line is correct, but the reconstruction is not properly formatted.
29	Partially correct	11 ms	7552 KB	First line is correct, but the reconstruction is not properly formatted.
30	Partially correct	12 ms	7552 KB	First line is correct, but the reconstruction is not properly formatted.
31	Partially correct	15 ms	7808 KB	First line is correct, but the reconstruction is not properly formatted.
32	Partially correct	11 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
33	Partially correct	20 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
34	Partially correct	18 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
35	Partially correct	17 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
36	Partially correct	19 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
37	Partially correct	27 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
38	Partially correct	25 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
39	Partially correct	26 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
40	Partially correct	23 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
41	Partially correct	16 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
42	Partially correct	18 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
43	Partially correct	15 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
44	Partially correct	18 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
45	Partially correct	18 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
46	Partially correct	17 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
47	Partially correct	13 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
48	Partially correct	20 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
49	Partially correct	23 ms	8448 KB	First line is correct, but the reconstruction is not properly formatted.
50	Partially correct	398 ms	10476 KB	First line is correct, but the reconstruction is not properly formatted.
51	Partially correct	4785 ms	10268 KB	First line is correct, but the reconstruction is not properly formatted.
52	Partially correct	404 ms	10752 KB	First line is correct, but the reconstruction is not properly formatted.
53	Partially correct	380 ms	10496 KB	First line is correct, but the reconstruction is not properly formatted.
54	Partially correct	386 ms	10488 KB	First line is correct, but the reconstruction is not properly formatted.
55	Partially correct	442 ms	10848 KB	First line is correct, but the reconstruction is not properly formatted.
56	Partially correct	419 ms	10744 KB	First line is correct, but the reconstruction is not properly formatted.
57	Partially correct	429 ms	10624 KB	First line is correct, but the reconstruction is not properly formatted.
58	Partially correct	3147 ms	10268 KB	First line is correct, but the reconstruction is not properly formatted.
59	Partially correct	364 ms	10368 KB	First line is correct, but the reconstruction is not properly formatted.
60	Partially correct	411 ms	10624 KB	First line is correct, but the reconstruction is not properly formatted.
61	Partially correct	326 ms	10484 KB	First line is correct, but the reconstruction is not properly formatted.
62	Partially correct	427 ms	10496 KB	First line is correct, but the reconstruction is not properly formatted.
63	Partially correct	405 ms	10752 KB	First line is correct, but the reconstruction is not properly formatted.
64	Partially correct	167 ms	9976 KB	First line is correct, but the reconstruction is not properly formatted.
65	Partially correct	423 ms	10692 KB	First line is correct, but the reconstruction is not properly formatted.
66	Partially correct	342 ms	10488 KB	First line is correct, but the reconstruction is not properly formatted.
67	Partially correct	396 ms	10848 KB	First line is correct, but the reconstruction is not properly formatted.
68	Partially correct	430 ms	10880 KB	First line is correct, but the reconstruction is not properly formatted.
69	Partially correct	418 ms	10616 KB	First line is correct, but the reconstruction is not properly formatted.
70	Partially correct	388 ms	10624 KB	First line is correct, but the reconstruction is not properly formatted.
71	Partially correct	439 ms	10968 KB	First line is correct, but the reconstruction is not properly formatted.
72	Partially correct	459 ms	10856 KB	First line is correct, but the reconstruction is not properly formatted.
73	Partially correct	468 ms	11024 KB	First line is correct, but the reconstruction is not properly formatted.
74	Partially correct	431 ms	10872 KB	First line is correct, but the reconstruction is not properly formatted.
75	Partially correct	458 ms	11060 KB	First line is correct, but the reconstruction is not properly formatted.