Submission #419033

#	Time	Username	Problem	Language	Result	Execution time	Memory
419033		JediMaster11	Rectangles (IOI19_rect)	C++17	37 / 100	5034 ms	24660 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 (val >= grid[y][j1 - 1] || val >= grid[y][j2 + 1] || val >= grid[i1 - 1][x] || val >= grid[i2 + 1][x])
                            {

                                works = false;
                            }

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

    return count;
}

• 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