Submission #5419

#	Time	Username	Problem	Language	Result	Execution time	Memory
5419		baneling100	Luxury burrow (IZhO13_burrow)	C++98	100 / 100	580 ms	5012 KiB

burrow

#include <stdio.h>
#define inf 0x7fffffff

int n, m, k, a[1001][1001], mmax, mmin=inf, ans1, ans2, s[1001][2], top, h[1001];

void input(void)
{
    int i, j;

    scanf("%d %d %d",&n,&m,&k);
    for(i=1 ; i<=n ; i++)
        for(j=1 ; j<=m ; j++)
        {
            scanf("%d",&a[i][j]);
            if(mmax<a[i][j])
                mmax=a[i][j];
            if(mmin>a[i][j])
                mmin=a[i][j];
        }
}

int find_rec(int num)
{
    int i, j, l, x, res=0;

    for(i=1 ; i<=m ; i++)
        h[i]=0;
    for(i=1 ; i<=n ; i++)
    {
        for(j=1 ; j<=m ; j++)
        {
            if(a[i][j]>=num)
                h[j]++;
            else
                h[j]=0;
        }
        top=0;
        for(j=1 ; j<=m ; j++)
        {
            x=j;
            while(top && s[top][0]>=h[j])
            {
                x=s[top][1];
                top--;
            }
            if(h[j])
            {
                s[++top][0]=h[j];
                s[top][1]=x;
            }
            for(l=1 ; l<=top ; l++)
            {
                x=s[l][0]*(j-s[l][1]+1);
                if(res<x)
                    res=x;
            }
        }
    }
    return res;
}

void process(void)
{
    int left=mmin, mid, right=mmax, temp;

    while(left<=right)
    {
        mid=(left+right)/2;
        temp=find_rec(mid);
        if(temp>=k)
        {
            ans1=mid;
            ans2=temp;
            left=mid+1;
        }
        else
            right=mid-1;
    }
}

void output(void)
{
    printf("%d %d",ans1,ans2);
}

int main(void)
{
    input();
    process();
    output();

    return 0;
}

• Subtask 1: 100 / 100