Submission #447381

#	Time	Username	Problem	Language	Result	Execution time	Memory
447381		dxz05	Rectangles (IOI19_rect)	C++14	37 / 100	1155 ms	67744 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 222;

bool good[N][N][N];

long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = a.size(), m = a[0].size();
	if (n < 3 || m < 3) return 0;

	if (n == 3){
	    int ans = 0;
	    for (int l = 1; l < m - 1; l++){
	        int mx = 0;
	        for (int r = l; r < m - 1; r++){
	            mx = max(mx, a[1][r]);
	            if (a[1][r] >= min(a[0][r], a[2][r])) break;
	            if (mx < min(a[1][l - 1], a[1][r + 1])) ans++;
	        }
	    }
	    return ans;
	}

	for (int i = 1; i < n - 1; i++){
	    for (int x = 1; x < m - 1; x++){
	        int mx = 0;
	        for (int y = x; y < m - 1; y++){
	            mx = max(mx, a[i][y]);
                if (mx < min(a[i][x - 1], a[i][y + 1])){
                    //cout << i << ' ' << x << ' ' << y << endl;
                    good[i][x][y] = true;
                }
	        }
	    }
	}

	int ans = 0;

	for (int i = 1; i < n - 1; i++){
	    for (int x = 1; x < m - 1; x++){
	        for (int y = x; y < m - 1; y++){
	            int j = i;
	            vector<int> v(m);
	            while (j < n - 1 && good[j][x][y]){
	                int cnt = 0;
	                for (int k = x; k <= y; k++){
	                    v[k] = max(v[k], a[j][k]);
	                    cnt += v[k] < min(a[i - 1][k], a[j + 1][k]);
	                }

	                if (cnt == y - x + 1) ans++;

	                j++;
	            }
	        }
	    }
	}

    return ans;
}

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