제출 #1211915

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211915		ProtonDecay314	Rectangles (IOI19_rect)	C++20	25 / 100	5094 ms	22852 KiB

rect

/*
TC: O(nm^2)
*/
#include "rect.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<bool> vb;

ll count_rect_top_left(const vvi& a, int miny, int minx) {
    ll ans = 0ll;
    int Y = a.size(), X = a[0].size();

    int maxy = Y - 2, maxx = X - 2;

    vi col_max(maxx - minx + 1, 0);

    vi row_max(maxy - miny + 1, 0);

    for(int y = miny; y <= maxy; y++) {
        for(int i = 0; i + miny <= y; i++) {
            row_max[i] = 0;
        }
        for(int x = minx; x <= maxx; x++) {
            col_max[x - minx] = max(col_max[x - minx], a[y][x]);
            for(int i = 0; i + miny <= y; i++) {
                row_max[i] = max(row_max[i], a[i + miny][x]);
            }

            // check if valid
            bool is_valid = true;
            
            // rows
            for(int i = 0; i + miny <= y; i++) {
                if(row_max[i] >= a[i + miny][minx - 1] || row_max[i] >= a[i + miny][x + 1]) {
                    is_valid = false;
                    break;
                }
            }

            // columns
            for(int i = 0; i + minx <= x; i++) {
                if(col_max[i] >= a[miny - 1][i + minx] || col_max[i] >= a[y + 1][i + minx]) {
                    is_valid = false;
                    break;
                }
            }

            if(is_valid) ans++;
        }
    }

    return ans;
}

ll count_rectangles(vvi a) {
    int rows = a.size(), cols = a[0].size();

    ll ans = 0ll;

    for(ll y = 1ll; y <= rows - 2ll; y++) {
        for(ll x = 1ll; x <= cols -2ll; x++) {
            ans += count_rect_top_left(a, y, x);
        }
    }

	return ans;
}

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