Submission #419022

#	Time	Username	Problem	Language	Result	Execution time	Memory
419022		JediMaster11	Rectangles (IOI19_rect)	C++17	0 / 100	5013 ms	25476 KiB

rect

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define vint vector<int>
#define vll vector<long long>
#define fo(a, b, c) for (int a = b; a < (int)c; a++)
#define rfo(a, b, c) for (int a = b - 1; a >= (int)c; a--)
#define print(x) cout << x << "\n"

ll count_rectangles(vector<vint> grid)
{
    int n = grid.size();
    int m = grid[0].size();
    bool done[n][m]; // ignore when done=true

    int max;

    // if its smaller than a side piece, ignore it in bool array
    // tallest in any row or grid can be ignored
    fo(i, 0, n)
    {
        max = -1;
        fo(j, 0, m)
        {
            if (grid[i][j] > max)
            {
                max = grid[i][j];
            }
        }
        fo(j, 0, m)
        {
            if (grid[i][j] == max)
            {
                done[i][j] = true;
            }
        }

        done[i][0] = true;
        done[i][m - 1] = true;

        if (grid[i][0] <= grid[i][1])
        {
            done[i][1] = true;
        }
        if (grid[i][m - 1] <= grid[i][m - 2])
        {
            done[i][m - 2] = true;
        }
    }

    fo(j, 0, m)
    {
        max = -1;
        // pos = -1;
        fo(i, 0, n)
        {
            if (grid[i][j] > max)
            {
                max = grid[i][j];
                // pos = i;
            }
        }

        fo(i, 0, n)
        {
            if (grid[i][j] == max)
            {
                done[i][j] = true;
            }
        }

        done[0][j] = true;
        done[n - 1][j] = true;

        if (grid[0][j] <= grid[1][j])
        {
            done[1][j] = true;
        }
        if (grid[n - 1][j] <= grid[n - 2][j])
        {
            done[n - 2][j] = true;
        }
    }
    ll count = 0;

    // vector<pair<int,int>> works;

    // fo(i,1,n-1){
    //     fo(j,1,m-1){
    //         if(!done[i][j]){

    //             int val = grid[i][j];

    //             if(val < grid[i][j+1] && val < grid[i][j-1] && val < grid[i+1][j] && val < grid[i-1][j]){

    //                 works.push_back({i,j});

    //             }
    //         }
    //     }
    // }
    // count = works.size();

    fo(i1, 1, n - 1)
    {
        fo(j1, 1, m - 1)
        {

            fo(i2, i1, n - 1)
            {
                fo(j2, j1, m - 1)
                {

                    bool works = true;

                    fo(y, i1, i2 + 1)
                    {
                        fo(x, j1, j2 + 1)
                        {
                            // int val = grid[y][x];
                            if (done[y][x])
                            {
                                works = false;
                            }
                            if (!(grid[y][x] < grid[y][j1 - 1] && grid[y][x] < grid[y][j2 + 1]))
                            {

                                works = false;
                            }
                            else if (!(grid[y][x] < grid[i1 - 1][x] && grid[y][x] < grid[i2 + 1][x]))
                            {

                                works = false;
                            }

                            if (!works)
                            {
                                break;
                            }
                        }
                        if (!works)
                        {
                            break;
                        }
                    }
                    if (works)
                    {
                        count++;
                        // print(i1 << " -> " << i2);
                        // print(j1 << " -> " << j2);
                        // print("");
                    }
                }
            }
        }
    }

    return count;
}

• 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