Submission #1080649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080649		speedcode	Rectangles (IOI19_rect)	C++17	0 / 100	587 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, largeur+m, 0);
            for (int a = i; a < n - 1; a++)
            {
                bool bad2 = false;
 
                for (int b = j; b < m - 1 ; b++)
                {
                    bool bad = false;
                        if(!isgoodHorizontal[a][j][b]){
                            bad = true;
                            largeur[b] = true;
                            break;
                        }
                    
 
                        if(!isgoodVertical[b][i][a]){
                            bad = true;
                            bad2 = true;
                            break;
                        }
                    
                    if(bad2) break;
                    if(largeur[b]) continue;
                    if(bad) continue;
                    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