제출 #823174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
823174		vjudge1	Rectangles (IOI19_rect)	C++17	37 / 100	2922 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 < m; ++ j) {
            M[j][i][i] = N[i][j][j] = a[i][j];
        }
    }

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

    for(int i = m - 2; i > 0; i --) {
        for(int j = i + 1; j < m - 1; ++ j) {
            for(int k = 1; k < n - 1; ++ 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;
                    }
                    bool ok = true;
                    for(int l = i; l <= ii; ++ l) {
                        if(min(a[l][j - 1], a[l][jj + 1]) <= N[l][j][jj]) {
                            ok = false;
                            break;
                        }
                    }
                    for(int r = j; r <= jj; ++ r) {
                        if(min(a[i - 1][r], a[ii + 1][r]) <= M[r][i][ii]) {
                            ok = false;
                            break;
                        }
                    }
                    cnt += ok;
                }
            }
        }
    }
    return cnt;
}

• 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