# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
5409 | gs12006 | Luxury burrow (IZhO13_burrow) | C++98 | 2000 ms | 15276 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <memory.h>
int a[1100][1100];
int s[1100][2];
int d[1100][1100];
int ans[1100][1100];
int n,m;
int f(int x)
{
int i,j,t,max=0;
for (i=0;i<n;i++) for (j=0;j<m;j++) ans[i][j]=0;
for (i=0;i<m;i++) if (a[0][i]>=x) d[0][i]=1;
for (i=0;i<m;i++) for (j=1;j<n;j++) if(a[j][i]>=x) d[j][i]=d[j-1][i]+1;
for (i=0;i<n;i++)
{
for (j=0;j<m;j++) if (d[i][j]>0)
{
t=0;
for (;d[i][j]!=0&&j<m;j++,t++)
{
for (;t>0&&s[t-1][0]>d[i][j];t--) ans[i][s[t-1][1]]+=j-s[t-1][1];
s[t][0]=d[i][j];
s[t][1]=j;
}
for (;t>0;t--) ans[i][s[t-1][1]]+=j-s[t-1][1];
}
for (j=m-1;j>=0;j--) if (d[i][j]>0)
{
t=0;
for (;d[i][j]!=0&&j>=0;j--,t++)
{
for (;t>0&&s[t-1][0]>d[i][j];t--) ans[i][s[t-1][1]]+=s[t-1][1]-j;
s[t][0]=d[i][j];
s[t][1]=j;
}
for (;t>0;t--) ans[i][s[t-1][1]]+=s[t-1][1]-j;
}
for (j=0;j<m;j++) if (ans[i][j]>0) ans[i][j]--;
for (j=0;j<m;j++) if (ans[i][j]>0) ans[i][j]*=d[i][j];
}
for (i=0;i<n;i++) for (j=0;j<m;j++) if (ans[i][j]>max) max=ans[i][j];
return max;
}
int main()
{
int i,j,k,minn=1<<30,maxn=0,midn,tt;
scanf("%d %d %d",&n,&m,&k);
for (i=0;i<n;i++) for (j=0;j<m;j++)
{
scanf("%d",&a[i][j]);
if (a[i][j]<minn) minn=a[i][j];
if (a[i][j]>maxn) maxn=a[i][j];
}
while (1)
{
if (maxn<=minn+1)
{
tt=f(maxn);
if (tt>=k) printf("%d %d",maxn,tt);
else printf("%d %d",minn,f(minn));
break;
}
midn=(maxn+minn)/2;
tt=f(midn);
if (tt>k) minn=midn;
else maxn=midn;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |