Submission #439331

#	Time	Username	Problem	Language	Result	Execution time	Memory
439331		Sorting	Rectangles (IOI19_rect)	C++17	0 / 100	5085 ms	22676 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;
typedef long long ll;

const int N = 2500 + 3;

vector<vector<int>> a;
int n, m;

bool check(int x1, int y1, int x2, int y2){
    for(int i = x1; i <= x2; ++i)
        for(int j = y1; j <= y2; ++j)
            if(a[i][j] >= a[x1 - 1][j] || a[i][j] >= a[x2 + 1][j] || a[i][j] >= a[i][y1 - 1] || a[i][j] >= a[i][y2 + 1])
                return false;
    return true; 
}

long long count_rectangles(vector<vector<int>> _a) {
    swap(a, _a);
	n = a.size(), m = a[0].size();

    ll ans = 0;
    for(int x1 = 1; x1 < n - 1; ++x1)
        for(int y1 = 1; y1 < m - 1; ++y1)
            for(int x2 = x1; x2 < n - 1; ++x2)
                for(int y2 = y1; y2 < m - 1; ++y2){
                    bool b = check(x1, y1, x2, y2);
                    if(!b) break;
                    ++ans;
                }
    return ans;
}

• 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