Submission #823097

#	Time	Username	Problem	Language	Result	Execution time	Memory
823097		vjudge1	Rectangles (IOI19_rect)	C++17	0 / 100	550 ms	1048576 KiB

rect

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

using namespace std;

long long count_rectangles(vector<vector<int> > a) {
	int n = a.size(),
        m = a[0].size();
    int N[n][m][m], 
        M[m][n][n];
    
    for(int i = 0; i < n; ++ i) {
        for(int j = 0; j < n; ++ j) {
            M[j][i][i] = N[i][j][j] = a[i][j];
        }
    }

    for(int i = 0; i < n; ++ i) {
        for(int j = i + 1; j < n; ++ j) {
            for(int k = 0; k < m; ++ k) {
                M[k][i][j] = max(M[k][i + 1][j], M[k][i][j - 1]);
            }
        }
    }

    for(int i = 0; i < m; ++ i) {
        for(int j = i + 1; j < m; ++ j) {
            for(int k = 0; k < n; ++ k) {
                N[k][i][j] = max(N[k][i + 1][j], N[k][i][j - 1]);
            }
        }
    }

    long long cnt = 0;
    for(int i = 1; i < n - 1; ++ i) {
        for(int j = 1; j < m - 1; ++ j) {
            for(int ii = i; ii < n - 1; ++ ii) {
                if(min(a[i - 1][j], a[ii + 1][j]) <= M[j][i][ii]) {
                    break;
                }
                for(int jj = j; jj < m - 1; ++ jj) {
                    if(min(a[i][j - 1], a[i][jj + 1]) <= N[i][j][jj]) {
                        break;
                    }
                    ++ cnt;
                }
            }
        }
    }
    return cnt;
}

• 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