제출 #396530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
396530		blue	Rectangles (IOI19_rect)	C++17	0 / 100	2184 ms	332 KiB

rect

#include "rect.h"
#include <vector>
using namespace std;


/*
For each (i, j)
T[i][j] = furthest row I such that T[I][j], T[I+1][j], ... T[i-1][j] all have height less than (i, j)
Similarly, D[i][j], R[i][j], L[i][j]

A rectangle (r1, r2, c1, c2) is good if(minD[r1-1][c1..c2] > r2) and so on
*/

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

    for(int r1 = 1; r1 <= n-2; r1++)
    {
        for(int r2 = r1; r2 <= n-2; r2++)
        {
            for(int c1 = 1; c1 <= m-2; c1++)
            {
                bool flag = 1;
                for(int i = r1; i <= r2; i++)
                {
                    if(a[i][c1] >= a[r1-1][c1] || a[i][c1] >= a[r2+1][c1])
                        flag = 0;
                }
                if(flag == 0) break;
                

                for(int c2 = c1; c2 <= m-2; c2++)
                {
                    bool flag = 1;
                    for(int i = r1; i <= r2; i++)
                    {
                        if(a[i][c2] >= a[r1-1][c2] || a[i][c2] >= a[r2+1][c2])
                            flag = 0;
                    }
                    if(flag == 0) break;

                    flag = 1;
                    for(int i = r1; i <= r2; i++)
                        for(int j = c1; j <= c2; j++)
                            flag &= (a[i][j] < a[i][c1-1]) && (a[i][j] < a[i][c2+1]);
                    if(flag) res++;
                }
            }
        }
    }

    return res;
}

• 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