Submission #895987

#	Time	Username	Problem	Language	Result	Execution time	Memory
895987		heeheeheehaaw	Luxury burrow (IZhO13_burrow)	C++17	0 / 100	2052 ms	20268 KiB

burrow

#include <iostream>
#define int long long

using namespace std;

int a[1005][1005];
int sp[1005][1005];
int n, m, k;

int partsum(int x1, int x2, int y1, int y2)
{
    return sp[x2][y2] - sp[x2][y1 - 1] - sp[x1 - 1][y2] + sp[x1 - 1][y1 - 1];
}

int calcarie(int x1, int x2, int y1, int y2)
{
    return (x2 - x1 + 1) * (y2 - y1 + 1);
}

int solve(int minn)
{
    int maxx = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            sp[i][j] = 0;
            if(a[i][j] >= minn)
                sp[i][j]++;
            sp[i][j] += sp[i - 1][j] + sp[i][j - 1] - sp[i - 1][j - 1];
        }

    for(int i = 1; i <= n; i++)
    {
        int le = -1;
        for(int j = 1; j <= m; j++)
        {
            if(a[i][j] < minn)
                le = -1;
            else
            {
                if(le == -1) le = j;
                int st = i, dr = n, pozj = i;
                while(st <= dr)
                {
                    int mij = (st + dr) / 2;
                    if(partsum(i, mij, le, j) == calcarie(i, mij, le, j))
                        pozj = mij, st = mij + 1;
                    else
                        dr = mij - 1;
                }

                dr = i, st = 1;
                int pozs = i;
                while(st <= dr)
                {
                    int mij = (st + dr) / 2;
                    if(partsum(mij, i, le, j) == calcarie(mij, i, le, j))
                        pozs = mij, dr = mij - 1;
                    else
                        st = mij + 1;
                }

                int arie = (j - le + 1) * (pozj - pozs + 1);
                maxx = max(maxx, arie);
            }
        }

        int ri = -1;
        for(int j = m; j >= 1; j--)
        {
            if(a[i][j] < minn)
                ri = -1;
            else
            {
                if(ri == -1) ri = j;
                int st = i, dr = n, pozj = i;
                while(st <= dr)
                {
                    int mij = (st + dr) / 2;
                    if(partsum(i, mij, j, ri) == calcarie(i, mij, j, ri))
                        pozj = mij, st = mij + 1;
                    else
                        dr = mij - 1;
                }

                dr = i, st = 1;
                int pozs = i;
                while(st <= dr)
                {
                    int mij = (st + dr) / 2;
                    if(partsum(mij, i, j, ri) == calcarie(i, mij, j, ri))
                        pozs = mij, dr = mij - 1;
                    else
                        st = mij + 1;
                }

                int arie = (ri - j + 1) * (pozj - pozs + 1);
                maxx = max(maxx, arie);
            }
        }
    }

    for(int j = 1; j <= m; j++)
    {
        int sus = -1;
        for(int i = 1; i <= n; i++)
        {
            if(a[i][j] < minn)
                sus = -1;
            else
            {
                if(sus == -1) sus = i;
                int st = j, dr = m, pozdr = j;
                while(st <= dr)
                {
                    int mij = (st + dr) / 2;
                    if(partsum(sus, i, j, mij) == calcarie(sus, i, j, mij))
                        pozdr = mij, st = mij + 1;
                    else
                        dr = mij - 1;
                }

                dr = j, st = 1;
                int pozst = j;
                while(st <= dr)
                {
                    int mij = (st + dr) / 2;
                    if(partsum(sus, i, mij, j) == calcarie(sus, i, mij, j))
                        pozst = mij, dr = mij - 1;
                    else
                        st = mij + 1;
                }

                int arie = (pozdr - pozst + 1) * (i - sus + 1);
                maxx = max(maxx, arie);
            }
        }

        int jos = -1;
        for(int i = n; i >= 1; i--)
        {
            if(a[i][j] < minn)
                jos = -1;
            else
            {
                if(jos == -1) jos = i;
                int st = j, dr = m, pozdr = j;
                while(st <= dr)
                {
                    int mij = (st + dr) / 2;
                    if(partsum(i, jos, j, mij) == calcarie(i, jos, j, mij))
                        pozdr = mij, st = mij + 1;
                    else
                        dr = mij - 1;
                }

                dr = j, st = 1;
                int pozst = j;
                while(st <= dr)
                {
                    int mij = (st + dr) / 2;
                    if(partsum(i, jos, mij, j) == calcarie(i, jos, mij, j))
                        pozst = mij, dr = mij - 1;
                    else
                        st = mij + 1;
                }

                int arie = (pozdr - pozst + 1) * (jos - i + 1);
                maxx = max(maxx, arie);
            }
        }
    }

    return maxx;
}

signed main()
{
    cin>>n>>m>>k;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin>>a[i][j];
    int st = 1, dr = 1e9, rez = 0, poz = 0;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        int maxx = solve(mij);

        if(maxx >= k)
            poz = mij, rez = maxx, st = mij + 1;
        else
            dr = mij - 1;
    }

    cout<<poz<<" "<<rez<<'\n';
    return 0;
}

• Subtask 1: 0 / 100