Submission #222897

#	Time	Username	Problem	Language	Result	Execution time	Memory
222897		MrDomino	Rectangles (IOI19_rect)	C++14	37 / 100	5074 ms	23672 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"

using namespace std;

typedef long long ll;

long long count_rectangles(vector<vector<int>> a)
{
    ll sol = 0;
    int n = (int) a.size();
    int m = (int) a[0].size();
    vector<vector<bool>> good(m);
    for (int i = 0; i < m; i++)
    {
        good[i].resize(m);
    }
    for (int r1 = 1; r1 < n - 1; r1++)
    {
        for (int i = 0; i < m; i++)
        {
            for (int j = i; j < m; j++)
            {
                good[i][j] = 1;
            }
        }
        vector<int> mx(m);
        for (int r2 = r1; r2 < n - 1; r2++)
        {
            for (int j = 0; j < m; j++)
            {
                mx[j] = max(mx[j], a[r2][j]);
            }
            for (int i = 0; i < m; i++)
            {
                int big = 0;
                for (int j = i; j < m; j++)
                {
                    big = max(big, a[r2][j]);
                    if (big >= min(a[r2][i - 1], a[r2][j + 1]))
                    {
                        good[i][j] = 0;
                    }
                }
            }
            vector<bool> ok(m);
            for (int j = 0; j < m; j++)
            {
                ok[j] = (mx[j] < min(a[r1 - 1][j], a[r2 + 1][j]));
            }
            for (int c1 = 1; c1 < m - 1; c1++)
            {
                if (ok[c1])
                {
                    for (int c2 = c1; c2 < m - 1; c2++)
                    {
                        if (ok[c2] == 0)
                        {
                            break;
                        }
                        if (good[c1][c2])
                        {
                            sol++;
                        }
                    }
                }
            }
        }
    }
    return sol;
}

• 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