Submission #419049

#	Time	Username	Problem	Language	Result	Execution time	Memory
419049		JediMaster11	Rectangles (IOI19_rect)	C++17	37 / 100	5087 ms	25480 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 smalln(vector<vint> grid){

//     int n = grid.size();
//     int m = grid[0].size();


//     ll count=0;

//     bool work=true;

//     int maxEdge = max(grid[1][0], grid[1][m-1]);

// //subtask 5
//     fo(i,1,m-1){
//         fo(j,i,m-1){
//             work=true;
//             fo(x,i,j+1){
//                 int val = grid[1][x];
//                 if(val >= grid[1][i-1] || val >= grid[0][x] || val >= grid[2][x] || val >= grid[1][j+1])
//                 {
//                     work=false;
//                     break;
//                 }
//             }
//             if(work){
//                 count++;
//             }
//         }
//     }

//     return count;
// }


ll count_rectangles(vector<vint> grid)
{


    int n = grid.size();
    int m = grid[0].size();

    if(n <=2 || m <= 2){
        return 0;
    }

    ll count = 0;

    // if(n==3){
    //     return smalln(grid);
    // }


    bool done[n][m]; // ignore when done=true

    memset(done, false, n*m);

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


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

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

    // 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