Submission #89107

#	Time	Username	Problem	Language	Result	Execution time	Memory
89107		nika	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	1130 ms	50644 KiB

burrow

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define pb push_back
#define li 1005
#define ii pair<int,int>
using namespace std;
int n,m,k,A[li][li],cur[li],ans,fa[li],sz[li];
vector<int> nxt[li];
int dsu(int x){
	if(fa[x]==x) return x;
	return fa[x]=dsu(fa[x]);
}
void union1(int a,int b){
	int s1=dsu(a);
	int s2=dsu(b);
	if(s1==s2) return ;
	if(sz[s1]<sz[s2]) swap(s1,s2);
	fa[s2]=s1;
	sz[s1]+=sz[s2];
	sz[s2]=0;
}
void solve(int ind){
	for(int i=0;i<=m;i++) nxt[i].clear();
	for(int i=1;i<=n;i++){
		nxt[cur[i]-ind].pb(i);
	}
	for(int i=1;i<=n;i++){
		fa[i]=-1;
		sz[i]=1;
	}
	for(int i=m;i>=1;i--){
		for(int j=0;j<(int)nxt[i].size();j++){
			int go=nxt[i][j];
			fa[go]=go;
			if(go>1 && fa[go-1]!=-1){
				union1(go,go-1);
			}
			if(go<n && fa[go+1]!=-1){
				union1(go,go+1);
			}
			ans=max(ans,i*sz[dsu(go)]);
		}
	}
}
int check(int x){
	ans=0;
	for(int i=1;i<=n;i++) cur[i]=m+1;
	for(int i=m;i>=1;i--){
		for(int j=1;j<=n;j++){
			if(A[j][i]<x) cur[j]=i;
		}
		solve(i);
	}
	return ans;
}
int main(){
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&A[i][j]);
		}
	}
	int bas=1,son=inf;
	while(bas<=son){
		int mid=(bas+son)/2;
		if(check(mid)>=k) bas=mid+1;
		else son=mid-1;
	}
	printf("%d %d",son,check(son));
	return 0;
}

Compilation message (stderr)

burrow.cpp: In function 'int main()':
burrow.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&m,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
burrow.cpp:65:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&A[i][j]);
    ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 100 / 100