Submission #1080612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080612		speedcode	Rectangles (IOI19_rect)	C++17	37 / 100	2301 ms	1048576 KiB

rect

#include <bits/stdc++.h>
using namespace std;

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

    int isgoodHorizontal[n][m][m];

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

    for (int i = 1; i < n - 1; i++)
    {
        for (int j = 1; j < m - 1; j++)
        {
            priority_queue<int> hi;
            for (int k = j; k < m - 1; k++)
            {
                hi.push(a[i][k]);
                if (a[i][j - 1] <= hi.top())
                    break;

                if (a[i][k + 1] <= hi.top())
                    continue;

                isgoodHorizontal[i][j][k] = 1;
            }
        }
    }


    int isgoodVertical[m][n][n];

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

    for (int i = 1; i < m - 1; i++)
    {
        for (int j = 1; j < n - 1; j++)
        {
            priority_queue<int> hi;
            for (int k = j; k < n - 1; k++)
            {
                hi.push(a[k][i]);
                if (a[j - 1][i] <= hi.top())
                    break;
                if (a[k + 1][i] <= hi.top())
                    continue;
                isgoodVertical[i][j][k] = 1;
            }
        }
    }


    long long res = 0;

    for (int i = 1; i < n - 1; i++)
    {
        for (int j = 1; j < m - 1; j++)
        {
            for (int a = i; a < n - 1; a++)
            {
                int bad2 = false;

                for (int b = j; b < m - 1 ; b++)
                {
                    bool bad = false;
                    for(int l = i; l <= a; l++){
                        if(!isgoodHorizontal[l][j][b]){
                            bad = true;
                            break;
                        }
                    }

                    for(int c = j; c <= b; c++){
                        if(!isgoodVertical[c][i][a]){
                            bad = true;
                            bad2 = true;
                            break;
                        }
                    }
                    if(bad2) break;
                    if(bad) continue;
                    res++;
                }
            }
        }
    }


    return res;
}

• 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