제출 #88113

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
88113		Pajaraja	Bomb (IZhO17_bomb)	C++17	37 / 100	1095 ms	69020 KiB

bomb

#include <bits/stdc++.h>
#define MAXN 2507
using namespace std;
bool t[MAXN][MAXN],r[MAXN][MAXN];
int p[MAXN][MAXN],d[MAXN][MAXN],n,m,lh,lv;
char s[MAXN][MAXN];
bool provera(int x,int y)
{
	for(int i=x;i<=n;i++) for(int j=y;j<=m;j++) r[i][j]=(p[i][j]-p[i-x][j]-p[i][j-y]+p[i-x][j-y]==x*y);
	for(int i=n;i>0;i--) for(int j=m;j>0;j--) d[i][j]=r[i][j]+d[i+1][j]+d[i][j+1]-d[i+1][j+1];
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(t[i][j] && d[i][j]-d[min(n+1,i+x)][j]-d[i][min(m+1,j+y)]+d[min(n+1,i+x)][min(m+1,j+y)]==0) return false;
	return true;
}
int binarna(int l,int r,int x)
{
	if(l==r) return l;
	int s=(l+r+1)/2;
	if(provera(s,x)) return binarna(s,r,x);
	return binarna(l,s-1,x);
}
int najres(int x) {return x*binarna(1,lv,x);}
int main()
{
	lh=lv=MAXN;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s[i]);
		for(int j=1;j<=m;j++) t[i][j]=(s[i][j-1]=='1'?1:0);
	}
	for(int i=1;i<=n;i++)
	{
		int cur=0;
		for(int j=1;j<=m;j++)
		{
			if(t[i][j]==0) {if(cur!=0) lh=min(lh,cur); cur=0;}
			else cur++;
		}
		if(cur!=0) lh=min(lh,cur);
	}
	for(int i=1;i<=m;i++)
	{
		int cur=0;
		for(int j=1;j<=n;j++)
		{
			if(t[j][i]==0) {if(cur!=0) lv=min(lv,cur); cur=0;}
			else cur++;
		}
		if(cur!=0) lv=min(lv,cur);
	}
	int sol=0;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) p[i][j]=t[i][j]+p[i-1][j]+p[i][j-1]-p[i-1][j-1];
	int l=1,r=lh;
	while(r-l>10)
	{
		int s1=(2*l+r)/3,s2=(l+2*r)/3;
		if(najres(s1)<najres(s2)) l=s1;
		else r=s2;
	}
	for(int i=l;i<=r;i++) sol=max(sol,najres(i));
	/*for(int i=1;i<=lv;i++)
	{
		while(!provera(i,lh)) lh--; 
		if(sol>lh*lv) break;
		sol=max(sol,lh*i);
	}*/
	printf("%d",sol);
}

컴파일 시 표준 에러 (stderr) 메시지

bomb.cpp: In function 'int main()':
bomb.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
bomb.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",s[i]);
   ~~~~~^~~~~~~~~~~

• Subtask 1: 37 / 100