Submission #1077641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077641		Ignut	Rectangles (IOI19_rect)	C++17	13 / 100	441 ms	442884 KiB

rect

// Ignut

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int INF = 1e9 + 123;

const int N = 2552;
int n, m;

int a[N][N];
bool used[N][N];

vector<pair<int, int>> delta = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

bool Good(int i, int j) {
    return i >= 0 && j >= 0 && i < n && j < m && !used[i][j] && a[i][j] == 0;
}

int sz;
int minh, maxh, minv, maxv;

void dfs(int i, int j) {
    used[i][j] = true;
    sz ++;
    minh = min(minh, j);
    maxh = max(maxh, j);
    minv = min(minv, i);
    maxv = max(maxv, i);
    for (auto [di, dj] : delta) {
        int ci = i + di, cj = j + dj;
        if (Good(ci, cj))
            dfs(ci, cj);
    }
}

ll count_rectangles(vector<vector<int>> A) {
    n = A.size(), m = A[0].size();
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            a[i][j] = A[i][j];

    int res = 0;
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < m; j ++) {
            if (used[i][j] || a[i][j] == 1) continue;
            sz = 0;
            minh = minv = INF;
            maxh = maxv = -INF;
            dfs(i, j);
            if (sz == (maxv - minv + 1) * (maxh - minh + 1) && minh > 0 && minv > 0 && maxh < m - 1 && maxv < n - 1)
                res ++;
        }
    }

    return res;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28