oj.uz

Submission #5414

# Submission time Handle Problem Language Result Execution time Memory
5414 2014-04-30T14:23:49 Z gs12006 Luxury burrow (IZhO13_burrow) C++
0 / 100
 0 ms 19568 KB 
#include <stdio.h>
#include <algorithm>
using namespace std;

int a[1100][1100];
int s[1100][2];
int d[1100][1100];
int ans[1100][1100];
int n,m;
int nl[1100000];

inline 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]=d[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()
{
	freopen("burrow.in","r",stdin);
	freopen("burrow.out","w",stdout);
	
	int i,j,k,minn=1<<30,maxn=0,midn,tt,rl;
	scanf("%d %d %d",&n,&m,&k);
	rl=n*m;
	for (i=0;i<n;i++) for (j=0;j<m;j++)
	{
		scanf("%d",&a[i][j]);
		nl[m*i+j]=a[i][j];
	}
	sort(nl,nl+n*m);
	for (i=0;i<n*m-1;i++)
	{
		if (nl[i]==nl[i+1])
		{
			nl[i]=1<<30;
			rl--;
		}
	}
	sort(nl,nl+n*m);
	minn=0;
	maxn=rl-1;
	while (1)
	{
		if (maxn<=minn+1)
		{
			tt=f(nl[maxn]);
			if (tt>=k) printf("%d %d",nl[maxn],tt);
			else printf("%d %d",nl[minn],f(nl[minn]));
			break;
		}
		midn=(maxn+minn)/2;
		tt=f(nl[midn]);
		if (tt>=k) minn=midn;
		else maxn=midn;
	}
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
2 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
3 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
4 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
5 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
6 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
7 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
8 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
9 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
10 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
11 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
12 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
13 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
14 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
15 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
16 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
17 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
18 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
19 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
20 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
21 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
22 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
23 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
24 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)
25 Runtime error 0 ms 19568 KB open (syscall #2) was called by the program (disallowed syscall)