oj.uz

Submission #172151

# Submission time Handle Problem Language Result Execution time Memory
172151 2019-12-31T11:42:27 Z MvC Bomb (IZhO17_bomb) C++11
50 / 100
 1000 ms 103928 KB 
//#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=2505;
const int mod=1e9+7;
using namespace std;
int n,m,i,j,cur,h[nmax][nmax],v[nmax][nmax],x,y,a[nmax][nmax],ad[nmax][nmax],b[nmax][nmax],rs,mid,l,r;
char c;
bool ok(int h,int w)
{
	int i,j,x;
	for(i=1;i<=n;i++)for(j=1;j<=m;j++)ad[i][j]=0;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(i<=n-h+1 && j<=m-w+1)
			{
				x=b[i+h-1][j+w-1]-b[i+h-1][j-1]-b[i-1][j+w-1]+b[i-1][j-1];
				if(x==h*w)
				{
					ad[i][j]++;
					ad[i][j+w]--;
					ad[i+h][j]--;
					ad[i+h][j+w]++;
				}
			}
			ad[i][j]+=ad[i-1][j]+ad[i][j-1]-ad[i-1][j-1];
			if(!ad[i][j] && a[i][j])return 0;
		}
	}
	return 1;
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			cin>>c;
			a[i][j]=(c=='1');
			b[i][j]=a[i][j]+b[i-1][j]+b[i][j-1]-b[i-1][j-1];
		}
	}
	x=y=inf;
	for(i=1;i<=n;i++)
	{
		for(j=m;j>=1;j--)
		{
			if(a[i][j])
			{
				h[i][j]=h[i][j+1]+1;
				if(!a[i][j-1])y=min(y,h[i][j]);
			}
		}
	}
	for(i=1;i<=m;i++)
	{
		for(j=n;j>=1;j--)
		{
			if(a[j][i])
			{
				v[j][i]=v[j+1][i]+1;
				if(!a[j-1][i])x=min(x,v[j][i]);
			}
		}
	}
	if(x==inf)rc(0);
	if(n*m>=1e6)rc(x*y);
	for(i=1;i<=x;i++)
	{
		l=1,r=y,cur=0;
		while(l<=r)
		{
			mid=(l+r)/2;
			if(ok(i,mid))cur=mid,l=mid+1;
			else r=mid-1;
		}
		rs=max(rs,i*cur);
	}
	cout<<rs<<endl;
	return 0;
}

Subtask #1
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 54 ms 50556 KB Output is correct
4 Correct 55 ms 50552 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 1 ms 760 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 636 KB Output is correct
13 Correct 2 ms 632 KB Output is correct
14 Correct 2 ms 760 KB Output is correct
15 Correct 2 ms 632 KB Output is correct
16 Correct 2 ms 760 KB Output is correct
17 Correct 4 ms 1788 KB Output is correct
18 Correct 3 ms 1528 KB Output is correct
19 Correct 5 ms 2040 KB Output is correct
20 Correct 5 ms 2040 KB Output is correct
21 Correct 3 ms 1272 KB Output is correct
22 Correct 4 ms 1656 KB Output is correct
23 Correct 6 ms 2168 KB Output is correct
24 Correct 5 ms 1912 KB Output is correct
25 Correct 8 ms 2552 KB Output is correct
26 Correct 8 ms 2552 KB Output is correct
27 Correct 12 ms 7800 KB Output is correct
28 Correct 16 ms 5624 KB Output is correct
29 Correct 359 ms 10360 KB Output is correct
30 Correct 287 ms 10744 KB Output is correct
31 Correct 180 ms 8188 KB Output is correct
32 Correct 221 ms 10104 KB Output is correct
33 Correct 447 ms 12152 KB Output is correct
34 Correct 17 ms 6264 KB Output is correct
35 Correct 50 ms 8824 KB Output is correct
36 Correct 464 ms 13304 KB Output is correct
37 Correct 2 ms 760 KB Output is correct
38 Correct 386 ms 103672 KB Output is correct
39 Correct 2 ms 760 KB Output is correct
40 Execution timed out 1085 ms 33656 KB Time limit exceeded
41 Correct 2 ms 760 KB Output is correct
42 Correct 13 ms 2552 KB Output is correct
43 Correct 342 ms 100344 KB Output is correct
44 Execution timed out 1081 ms 12792 KB Time limit exceeded
45 Incorrect 338 ms 101112 KB Output isn't correct
46 Correct 326 ms 103644 KB Output is correct
47 Incorrect 342 ms 101112 KB Output isn't correct
48 Incorrect 332 ms 103676 KB Output isn't correct
49 Correct 393 ms 103416 KB Output is correct
50 Incorrect 343 ms 103452 KB Output isn't correct
51 Incorrect 329 ms 103288 KB Output isn't correct
52 Incorrect 335 ms 103280 KB Output isn't correct
53 Incorrect 331 ms 102644 KB Output isn't correct
54 Incorrect 282 ms 89976 KB Output isn't correct
55 Incorrect 282 ms 89628 KB Output isn't correct
56 Correct 376 ms 103032 KB Output is correct
57 Incorrect 274 ms 84488 KB Output isn't correct
58 Incorrect 281 ms 89652 KB Output isn't correct
59 Incorrect 277 ms 86520 KB Output isn't correct
60 Correct 320 ms 95096 KB Output is correct
61 Correct 396 ms 103216 KB Output is correct
62 Correct 393 ms 103848 KB Output is correct
63 Correct 385 ms 103744 KB Output is correct
64 Correct 274 ms 86648 KB Output is correct
65 Incorrect 331 ms 102860 KB Output isn't correct
66 Incorrect 326 ms 99576 KB Output isn't correct
67 Incorrect 339 ms 103800 KB Output isn't correct
68 Incorrect 345 ms 103928 KB Output isn't correct
69 Incorrect 275 ms 83832 KB Output isn't correct
70 Incorrect 154 ms 53480 KB Output isn't correct
71 Incorrect 257 ms 76664 KB Output isn't correct
72 Incorrect 270 ms 82052 KB Output isn't correct
73 Incorrect 272 ms 82168 KB Output isn't correct
74 Incorrect 270 ms 82936 KB Output isn't correct
75 Incorrect 276 ms 85496 KB Output isn't correct
76 Incorrect 285 ms 86192 KB Output isn't correct
77 Incorrect 283 ms 86728 KB Output isn't correct
78 Incorrect 284 ms 86952 KB Output isn't correct
79 Incorrect 209 ms 59512 KB Output isn't correct
80 Incorrect 211 ms 60664 KB Output isn't correct
81 Incorrect 215 ms 61128 KB Output isn't correct
82 Incorrect 291 ms 90300 KB Output isn't correct
83 Incorrect 318 ms 89336 KB Output isn't correct
84 Incorrect 209 ms 55184 KB Output isn't correct
85 Incorrect 287 ms 88204 KB Output isn't correct
86 Incorrect 368 ms 101348 KB Output isn't correct
87 Incorrect 279 ms 86772 KB Output isn't correct
88 Incorrect 293 ms 87608 KB Output isn't correct
89 Incorrect 315 ms 95872 KB Output isn't correct
90 Incorrect 181 ms 67704 KB Output isn't correct
91 Incorrect 299 ms 91128 KB Output isn't correct
92 Incorrect 313 ms 92792 KB Output isn't correct
93 Incorrect 364 ms 99732 KB Output isn't correct
94 Incorrect 314 ms 94456 KB Output isn't correct
95 Incorrect 290 ms 88568 KB Output isn't correct
96 Incorrect 292 ms 87916 KB Output isn't correct
97 Incorrect 386 ms 100472 KB Output isn't correct
98 Incorrect 324 ms 87772 KB Output isn't correct
99 Incorrect 350 ms 93816 KB Output isn't correct
100 Incorrect 368 ms 99292 KB Output isn't correct