Submission #933108

#	Time	Username	Problem	Language	Result	Execution time	Memory
933108		sleepntsheep	Luxury burrow (IZhO13_burrow)	C11	100 / 100	450 ms	18000 KiB

burrow

#include<stdio.h>
int hi(int a,int b){return a>b?a:b;}
int sz,n,m,k,a[1002][1002],b[1002][1002],st[1002],top,nl[1002],pl[1002];
int ok(int lo)
{
    for(int i=0;i++<n;)for(int j=0;j++<m;)b[i][j]=a[i][j]>=lo;
    for(int i=0;i++<n;)for(int j=0;j++<m;)
        if(b[i][j])b[i][j]+=b[i-1][j];
    int hisz=0;
    for(int i=0;i++<n;)
    {
        int*h=b[i];
        for(int j=0;j++<m;)
        {
            while(top&&h[j]<h[st[top]])nl[st[top--]]=j;
            st[++top]=j;
        }
        while(top)nl[st[top--]]=m+1;
        for(int j=m;j>=1;--j)
        {
            while(top&&h[j]<h[st[top]])pl[st[top--]]=j;
            st[++top]=j;
        }
        while(top)pl[st[top--]]=0;
        for(int j=0;j++<m;)
            hisz=hi(hisz,h[j]*(nl[j]-pl[j]-1));
    }
    return hisz>=k?sz=hisz,1:0;
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i++<n;)for(int j=0;j++<m;)scanf("%d",a[i]+j);

    ok(10);
    int l=0,r=1e9;
    while(l<=r){
        int y=(l+r)/2;
        if(ok(y))l=y+1;else r=y-1;
    }
    printf("%d %d",l-1,sz);
}

Compilation message (stderr)

burrow.c: In function 'main':
burrow.c:33:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d%d%d",&n,&m,&k);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~
burrow.c:34:43: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     for(int i=0;i++<n;)for(int j=0;j++<m;)scanf("%d",a[i]+j);
      |                                           ^~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100