Submission #591328

#	Time	Username	Problem	Language	Result	Execution time	Memory
591328		lcj	Rectangles (IOI19_rect)	C++17	13 / 100	1123 ms	526900 KiB

rect

#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

int n, m;
vector<vector<int>> field;
vector<vector<vector<pii>>> dp;

pii bound(int x, int y, int type) {
    if (field[x][y] == 1) return {0, 0};
    if (x == 0 || x == n-1 || y == 0 || y == m-1) return {-1, -1};
    if (dp[x][y][type].fi != -2) {
        return dp[x][y][type];
    }

    vector<tuple<int, int, int>> nexts = {{x+1, y, 3}, {x, y+1, 3}};
    if (type == 0) {
        if (field[x][y-1] == 0) return {-1, -1};
        if (field[x-1][y] == 0) return {-1, -1};
        get<2>(nexts[0]) = 1;
        get<2>(nexts[1]) = 2;
    }
    else if (type == 1) {
        if (field[x][y-1] == 0) return {-1, -1};
        get<2>(nexts[0]) = 1;
    }
    else if (type == 2) {
        if (field[x-1][y] == 0) return {-1, -1};
        get<2>(nexts[1]) = 2;
    }
    vector<pii> res;
    for (auto &i : nexts) {
        res.push_back(bound(get<0>(i), get<1>(i), get<2>(i)));
    }
    pii re = {res[0].fi+1, res[1].se+1};
    if (res[0].fi == -1 || res[1].fi == -1) re = {-1, -1};
    if (res[1].fi != 0 && res[0].fi+1 != res[1].fi) re = {-1, -1};
    if (res[0].se != 0 && res[1].se+1 != res[0].se) re = {-1, -1};
    dp[x][y][type] = re;
    return re;
}

ll count_rectangles(vector<vector<int> > a) {
    field = a;
    n = a.size(); m = a[0].size();
    ll cmax = 0;
    dp.assign(n, vector<vector<pii>>(m, vector<pii>(4, {-2, -2})));
    for (int i1 = 1; i1 < n-1; i1++)
    {
        for (int j1 = 1; j1 < m-1; j1++)
        {
            auto res = bound(i1, j1, 0);
            if (res.fi > 0) {
                cmax++;
            }
        }
    }
	return cmax;
}

• 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