Submission #1080654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080654		speedcode	Rectangles (IOI19_rect)	C++17	37 / 100	5092 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();

    bool 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;
            }
        }
    }

    bool 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++)
        {
            bool largeur[m];
            fill(largeur+1, largeur + m-1, 0);
            for (int a = i; a < n - 1; a++)
            {
                bool bad2 = false;

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

                    if (!isgoodVertical[b][i][a])
                    {
                        bad = true;
                        bad2 = true;
                    }

                    if (bad2)
                        continue;
                    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