제출 #1055200

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1055200		RecursiveCo	Rectangles (IOI19_rect)	C++17	0 / 100	1 ms	348 KiB

rect

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> pref;

int query(int r1, int c1, int r2, int c2) {
    int val = pref[r2][c2];
    val -= (c1? pref[r2][c1 - 1]: 0);
    val -= (r1? pref[r1 - 1][c2]: 0);
    val += (c1 && r1? pref[r1 - 1][c1 - 1]: 0);
    return val;
}

long long count_rectangles(vector<vector<int>> grid) {
    int n = grid.size();
    int m = grid[0].size();
    int maxi = -1;
    for (int i = 0; i < n; i++) maxi = max(maxi, *max_element(grid[i].begin(), grid[i].end()));
    if (maxi <= 1) {
        // Subtask 6
        pref.resize(n, vector<int>(m, 0));
        for (int i = 0; i < n; i++) {
            int prefhere = 0;
            for (int j = 0; j < m; j++) {
                prefhere += grid[i][j];
                pref[i][j] = (i? pref[i - 1][j]: 0) + prefhere;
            }
        }
        vector<vector<int>> left(n, vector<int>(m, 0));
        vector<vector<int>> above(n, vector<int>(m, 0));
        for (int i = 0; i < n; i++) {
            int here = -1;
            for (int j = 0; j < m; j++) {
                if (grid[i][j]) here = j;
                left[i][j] = here;
            }
        }
        for (int j = 0; j < m; j++) {
            int here = -1;
            for (int i = 0; i < n; i++) {
                if (grid[i][j]) here = j;
                above[i][j] = here;
            }
        }
        long long ans = 0;
        for (int i = 1; i < n - 1; i++) {
            for (int j = 1; j < m - 1; j++) {
                if (!grid[i][j] && grid[i + 1][j] && grid[i][j + 1] && left[i][j] != -1 && above[i][j] != -1) {
                    int l = left[i][j];
                    int t = above[i][j];
                    int bottom = query(i + 1, l + 1, i + 1, j);
                    int top = query(t, l + 1, t, j);
                    int leftside = query(t + 1, l, i, l);
                    int rightside = query(t + 1, j + 1, i, j + 1);
                    int inside = query(t + 1, l + 1, i, j);
                    if (bottom == j - l && top == j - l && leftside == i - t && rightside == i - t && !inside) ans++;
                }
            }
        }
        return ans;
    }
    return 0; // for subtasks I'm not solving.
}

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