Submission #5410

#TimeUsernameProblemLanguageResultExecution timeMemory
5410gs12006Luxury burrow (IZhO13_burrow)C++98
0 / 100
2000 ms15276 KiB
#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 timeMemoryGrader output
Fetching results...