Submission #823134

#	Time	Username	Problem	Language	Result	Execution time	Memory
823134		vjudge1	Rectangles (IOI19_rect)	C++17	0 / 100	42 ms	73812 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 < m; ++ 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(a[i - 1][j] <= a[ii][j]) {
                    break;
                }
                for(int jj = j; jj < m - 1; ++ jj) {
                    if(a[i][j - 1] <= a[i][jj]) {
                        break;
                    }
                    if(M[j][i][ii] < a[ii + 1][j] && N[i][j][jj] < a[i][jj + 1]) {
                        ++ 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