Submission #447376

#	Time	Username	Problem	Language	Result	Execution time	Memory
447376		dxz05	Rectangles (IOI19_rect)	C++14	27 / 100	1195 ms	67896 KiB

rect

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

using namespace std;

const int N = 202;

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

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

	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: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28