oj.uz

Submission #219790

# Submission time Handle Problem Language Result Execution time Memory
219790 2020-04-06T11:37:27 Z VEGAnn Rectangles (IOI19_rect) C++14
50 / 100
 5000 ms 318712 KB 
#include <bits/stdc++.h>
#include "rect.h"
#define all(x) x.begin(),x.end()
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int N = 2600;
const int oo = 2e9;
bool mrk[N][N];
int n, m, kol = 0, mx, my, Mx, My;
ll ans = 0, big = 0;

void dfs(int x, int y){
    if (mrk[x][y]) return;
    kol++;
    mrk[x][y] = 1;
    mx = min(mx, x);
    my = min(my, y);
    Mx = max(Mx, x);
    My = max(My, y);

    if (x > 0) dfs(x - 1, y);
    if (y > 0) dfs(x, y - 1);
    if (y < m - 1) dfs(x, y + 1);
    if (x < n - 1) dfs(x + 1, y);
}

long long count_rectangles(std::vector<std::vector<int> > a) {
    n = sz(a);
    m = sz(a[0]);

    for (int x = 1; x <= n; x++)
        for (int y = 1; y <= m; y++)
            big += (n / x) * (m / y);

    if (n < 3 || m < 3) return 0;

    bool ok = 1;

    for (int i = 0; i < n && ok; i++)
        for (int j = 0; j < m && ok; j++) {
            ok &= bool(a[i][j] < 2);
            mrk[i][j] = a[i][j];
        }

    if (ok){
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (!mrk[i][j]){
                    mx = my = oo;
                    Mx = My = -oo;
                    kol = 0;

                    dfs(i, j);

                    if ((Mx - mx + 1) * (My - my + 1) == kol && mx > 0 && my > 0 && Mx < n - 1 && My < m - 1)
                        ans++;
                }
        return ans;
    }

    for (int r1 = 1; r1 < n - 1; r1++)
    for (int r2 = r1; r2 < n - 1; r2++)
    for (int c1 = 1; c1 < m - 1; c1++)
    for (int c2 = c1; c2 < m - 1; c2++){
        bool ok = 1;

        for (int i = r1; i <= r2 && ok; i++)
        for (int j = c1; j <= c2 && ok; j++){
            ok &= bool(a[i][j] < a[i][c1 - 1]);
            ok &= bool(a[i][j] < a[i][c2 + 1]);
            ok &= bool(a[i][j] < a[r2 + 1][j]);
            ok &= bool(a[i][j] < a[r1 - 1][j]);
        }

        ans += ok;
    }

    assert(ans <= big);

	return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 6 ms 256 KB Output is correct
3 Correct 6 ms 256 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 256 KB Output is correct
17 Correct 4 ms 256 KB Output is correct
18 Correct 8 ms 256 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 4 ms 256 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 6 ms 256 KB Output is correct
3 Correct 6 ms 256 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 256 KB Output is correct
17 Correct 78 ms 384 KB Output is correct
18 Correct 80 ms 384 KB Output is correct
19 Correct 78 ms 384 KB Output is correct
20 Correct 65 ms 384 KB Output is correct
21 Correct 66 ms 384 KB Output is correct
22 Correct 66 ms 456 KB Output is correct
23 Correct 66 ms 384 KB Output is correct
24 Correct 20 ms 384 KB Output is correct
25 Correct 4 ms 256 KB Output is correct
26 Correct 8 ms 256 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 4 ms 256 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 6 ms 256 KB Output is correct
3 Correct 6 ms 256 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 256 KB Output is correct
17 Correct 78 ms 384 KB Output is correct
18 Correct 80 ms 384 KB Output is correct
19 Correct 78 ms 384 KB Output is correct
20 Correct 65 ms 384 KB Output is correct
21 Correct 66 ms 384 KB Output is correct
22 Correct 66 ms 456 KB Output is correct
23 Correct 66 ms 384 KB Output is correct
24 Correct 20 ms 384 KB Output is correct
25 Correct 2877 ms 1016 KB Output is correct
26 Correct 2885 ms 896 KB Output is correct
27 Correct 2932 ms 992 KB Output is correct
28 Correct 2302 ms 800 KB Output is correct
29 Correct 2561 ms 888 KB Output is correct
30 Correct 2605 ms 1028 KB Output is correct
31 Correct 2510 ms 924 KB Output is correct
32 Correct 2451 ms 1016 KB Output is correct
33 Correct 4 ms 256 KB Output is correct
34 Correct 8 ms 256 KB Output is correct
35 Correct 5 ms 384 KB Output is correct
36 Correct 5 ms 384 KB Output is correct
37 Correct 4 ms 256 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 6 ms 256 KB Output is correct
3 Correct 6 ms 256 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 256 KB Output is correct
17 Correct 78 ms 384 KB Output is correct
18 Correct 80 ms 384 KB Output is correct
19 Correct 78 ms 384 KB Output is correct
20 Correct 65 ms 384 KB Output is correct
21 Correct 66 ms 384 KB Output is correct
22 Correct 66 ms 456 KB Output is correct
23 Correct 66 ms 384 KB Output is correct
24 Correct 20 ms 384 KB Output is correct
25 Correct 2877 ms 1016 KB Output is correct
26 Correct 2885 ms 896 KB Output is correct
27 Correct 2932 ms 992 KB Output is correct
28 Correct 2302 ms 800 KB Output is correct
29 Correct 2561 ms 888 KB Output is correct
30 Correct 2605 ms 1028 KB Output is correct
31 Correct 2510 ms 924 KB Output is correct
32 Correct 2451 ms 1016 KB Output is correct
33 Execution timed out 5084 ms 4736 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 384 KB Output is correct
2 Correct 22 ms 384 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 25 ms 384 KB Output is correct
6 Correct 26 ms 384 KB Output is correct
7 Correct 25 ms 384 KB Output is correct
8 Correct 25 ms 560 KB Output is correct
9 Correct 25 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 103 ms 26488 KB Output is correct
3 Correct 219 ms 56188 KB Output is correct
4 Correct 215 ms 56312 KB Output is correct
5 Correct 216 ms 56312 KB Output is correct
6 Correct 181 ms 112888 KB Output is correct
7 Correct 376 ms 268792 KB Output is correct
8 Correct 417 ms 318712 KB Output is correct
9 Correct 4 ms 256 KB Output is correct
10 Correct 8 ms 256 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 256 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 6 ms 256 KB Output is correct
3 Correct 6 ms 256 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 256 KB Output is correct
17 Correct 78 ms 384 KB Output is correct
18 Correct 80 ms 384 KB Output is correct
19 Correct 78 ms 384 KB Output is correct
20 Correct 65 ms 384 KB Output is correct
21 Correct 66 ms 384 KB Output is correct
22 Correct 66 ms 456 KB Output is correct
23 Correct 66 ms 384 KB Output is correct
24 Correct 20 ms 384 KB Output is correct
25 Correct 2877 ms 1016 KB Output is correct
26 Correct 2885 ms 896 KB Output is correct
27 Correct 2932 ms 992 KB Output is correct
28 Correct 2302 ms 800 KB Output is correct
29 Correct 2561 ms 888 KB Output is correct
30 Correct 2605 ms 1028 KB Output is correct
31 Correct 2510 ms 924 KB Output is correct
32 Correct 2451 ms 1016 KB Output is correct
33 Execution timed out 5084 ms 4736 KB Time limit exceeded
34 Halted 0 ms 0 KB -