oj.uz

Submission #220631

# Submission time Handle Problem Language Result Execution time Memory
220631 2020-04-08T10:14:34 Z Vimmer Skandi (COCI20_skandi) C++14
55 / 110
 7119 ms 12280 KB 
#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 300001
#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++)
    {
        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

# Verdict Execution time Memory Grader output
1 Partially correct 2532 ms 8908 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 2589 ms 8920 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 2447 ms 8952 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 2521 ms 8832 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 2503 ms 8952 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 2435 ms 8912 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 2553 ms 8912 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 2529 ms 8832 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 2518 ms 8832 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 2561 ms 8912 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 2434 ms 8916 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 2560 ms 8912 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 2487 ms 8952 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 2527 ms 8952 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 2534 ms 8904 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 2518 ms 8912 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 2499 ms 8952 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 2508 ms 8928 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 2517 ms 8952 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 2553 ms 8952 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 2483 ms 8908 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 2562 ms 8952 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 2522 ms 8916 KB First line is correct, but the reconstruction is not properly formatted.

Subtask #2
16.0 / 32.0

# Verdict Execution time Memory Grader output
1 Partially correct 2507 ms 9728 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 2483 ms 9216 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 2495 ms 9624 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 2519 ms 9244 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 2428 ms 9236 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 2544 ms 9208 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 2442 ms 9092 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 2539 ms 9272 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 2532 ms 9976 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 2562 ms 9856 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 2569 ms 9856 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 2454 ms 9856 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 2449 ms 9976 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 2480 ms 9976 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 2605 ms 9944 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 2746 ms 9940 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 2796 ms 9944 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 2600 ms 9856 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 2476 ms 9940 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 2669 ms 9940 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 2507 ms 9856 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 2668 ms 9936 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 2600 ms 9932 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 2655 ms 9936 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 2649 ms 9936 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 2531 ms 9940 KB First line is correct, but the reconstruction is not properly formatted.

Subtask #3
30.0 / 60.0

# Verdict Execution time Memory Grader output
1 Partially correct 2532 ms 8908 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 2589 ms 8920 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 2447 ms 8952 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 2521 ms 8832 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 2503 ms 8952 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 2435 ms 8912 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 2553 ms 8912 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 2529 ms 8832 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 2518 ms 8832 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 2561 ms 8912 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 2434 ms 8916 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 2560 ms 8912 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 2487 ms 8952 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 2527 ms 8952 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 2534 ms 8904 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 2518 ms 8912 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 2499 ms 8952 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 2508 ms 8928 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 2517 ms 8952 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 2553 ms 8952 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 2483 ms 8908 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 2562 ms 8952 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 2522 ms 8916 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 2507 ms 9728 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 2483 ms 9216 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 2495 ms 9624 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 2519 ms 9244 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 2428 ms 9236 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 2544 ms 9208 KB First line is correct, but the reconstruction is not properly formatted.
30 Partially correct 2442 ms 9092 KB First line is correct, but the reconstruction is not properly formatted.
31 Partially correct 2539 ms 9272 KB First line is correct, but the reconstruction is not properly formatted.
32 Partially correct 2532 ms 9976 KB First line is correct, but the reconstruction is not properly formatted.
33 Partially correct 2562 ms 9856 KB First line is correct, but the reconstruction is not properly formatted.
34 Partially correct 2569 ms 9856 KB First line is correct, but the reconstruction is not properly formatted.
35 Partially correct 2454 ms 9856 KB First line is correct, but the reconstruction is not properly formatted.
36 Partially correct 2449 ms 9976 KB First line is correct, but the reconstruction is not properly formatted.
37 Partially correct 2480 ms 9976 KB First line is correct, but the reconstruction is not properly formatted.
38 Partially correct 2605 ms 9944 KB First line is correct, but the reconstruction is not properly formatted.
39 Partially correct 2746 ms 9940 KB First line is correct, but the reconstruction is not properly formatted.
40 Partially correct 2796 ms 9944 KB First line is correct, but the reconstruction is not properly formatted.
41 Partially correct 2600 ms 9856 KB First line is correct, but the reconstruction is not properly formatted.
42 Partially correct 2476 ms 9940 KB First line is correct, but the reconstruction is not properly formatted.
43 Partially correct 2669 ms 9940 KB First line is correct, but the reconstruction is not properly formatted.
44 Partially correct 2507 ms 9856 KB First line is correct, but the reconstruction is not properly formatted.
45 Partially correct 2668 ms 9936 KB First line is correct, but the reconstruction is not properly formatted.
46 Partially correct 2600 ms 9932 KB First line is correct, but the reconstruction is not properly formatted.
47 Partially correct 2655 ms 9936 KB First line is correct, but the reconstruction is not properly formatted.
48 Partially correct 2649 ms 9936 KB First line is correct, but the reconstruction is not properly formatted.
49 Partially correct 2531 ms 9940 KB First line is correct, but the reconstruction is not properly formatted.
50 Partially correct 2564 ms 11688 KB First line is correct, but the reconstruction is not properly formatted.
51 Partially correct 7119 ms 11728 KB First line is correct, but the reconstruction is not properly formatted.
52 Partially correct 2644 ms 12024 KB First line is correct, but the reconstruction is not properly formatted.
53 Partially correct 2674 ms 11764 KB First line is correct, but the reconstruction is not properly formatted.
54 Partially correct 2684 ms 11512 KB First line is correct, but the reconstruction is not properly formatted.
55 Partially correct 2693 ms 12020 KB First line is correct, but the reconstruction is not properly formatted.
56 Partially correct 2604 ms 11868 KB First line is correct, but the reconstruction is not properly formatted.
57 Partially correct 2659 ms 11820 KB First line is correct, but the reconstruction is not properly formatted.
58 Partially correct 5705 ms 11704 KB First line is correct, but the reconstruction is not properly formatted.
59 Partially correct 2582 ms 11600 KB First line is correct, but the reconstruction is not properly formatted.
60 Partially correct 2564 ms 11860 KB First line is correct, but the reconstruction is not properly formatted.
61 Partially correct 2625 ms 11800 KB First line is correct, but the reconstruction is not properly formatted.
62 Partially correct 2538 ms 11896 KB First line is correct, but the reconstruction is not properly formatted.
63 Partially correct 2572 ms 11920 KB First line is correct, but the reconstruction is not properly formatted.
64 Partially correct 2748 ms 11268 KB First line is correct, but the reconstruction is not properly formatted.
65 Partially correct 2545 ms 11896 KB First line is correct, but the reconstruction is not properly formatted.
66 Partially correct 2544 ms 11732 KB First line is correct, but the reconstruction is not properly formatted.
67 Partially correct 2550 ms 12080 KB First line is correct, but the reconstruction is not properly formatted.
68 Partially correct 2624 ms 12068 KB First line is correct, but the reconstruction is not properly formatted.
69 Partially correct 2502 ms 11900 KB First line is correct, but the reconstruction is not properly formatted.
70 Partially correct 2627 ms 11852 KB First line is correct, but the reconstruction is not properly formatted.
71 Partially correct 2543 ms 12140 KB First line is correct, but the reconstruction is not properly formatted.
72 Partially correct 2688 ms 12024 KB First line is correct, but the reconstruction is not properly formatted.
73 Partially correct 2554 ms 12184 KB First line is correct, but the reconstruction is not properly formatted.
74 Partially correct 2547 ms 12152 KB First line is correct, but the reconstruction is not properly formatted.
75 Partially correct 2562 ms 12280 KB First line is correct, but the reconstruction is not properly formatted.