oj.uz

Submission #172154

# Submission time Handle Problem Language Result Execution time Memory
172154 2019-12-31T11:47:54 Z MvC Bomb (IZhO17_bomb) C++11
50 / 100
 1000 ms 103812 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);
		if((ld)(clock()/CLOCKS_PER_SEC)>0.9)rc(rs);
	}
	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 760 KB Output is correct
3 Correct 52 ms 50604 KB Output is correct
4 Correct 55 ms 50480 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 380 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 3 ms 764 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 2 ms 636 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 1784 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 1144 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 2424 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 10460 KB Output is correct
30 Correct 284 ms 10768 KB Output is correct
31 Correct 168 ms 8184 KB Output is correct
32 Correct 217 ms 10104 KB Output is correct
33 Correct 442 ms 12200 KB Output is correct
34 Correct 17 ms 6136 KB Output is correct
35 Correct 51 ms 8824 KB Output is correct
36 Correct 462 ms 13432 KB Output is correct
37 Correct 2 ms 760 KB Output is correct
38 Correct 385 ms 103396 KB Output is correct
39 Correct 2 ms 760 KB Output is correct
40 Execution timed out 1006 ms 33696 KB Time limit exceeded
41 Correct 2 ms 760 KB Output is correct
42 Correct 13 ms 2552 KB Output is correct
43 Correct 346 ms 98592 KB Output is correct
44 Execution timed out 1002 ms 12880 KB Time limit exceeded
45 Incorrect 344 ms 100904 KB Output isn't correct
46 Correct 322 ms 103448 KB Output is correct
47 Incorrect 361 ms 101032 KB Output isn't correct
48 Incorrect 334 ms 103544 KB Output isn't correct
49 Correct 386 ms 103752 KB Output is correct
50 Incorrect 338 ms 103752 KB Output isn't correct
51 Incorrect 336 ms 103644 KB Output isn't correct
52 Incorrect 340 ms 103672 KB Output isn't correct
53 Incorrect 331 ms 103032 KB Output isn't correct
54 Incorrect 280 ms 90456 KB Output isn't correct
55 Incorrect 279 ms 87068 KB Output isn't correct
56 Correct 386 ms 103812 KB Output is correct
57 Incorrect 272 ms 82040 KB Output isn't correct
58 Incorrect 287 ms 87160 KB Output isn't correct
59 Incorrect 276 ms 83956 KB Output isn't correct
60 Correct 319 ms 95380 KB Output is correct
61 Correct 391 ms 103156 KB Output is correct
62 Correct 389 ms 102140 KB Output is correct
63 Correct 385 ms 102220 KB Output is correct
64 Correct 281 ms 85240 KB Output is correct
65 Incorrect 325 ms 101308 KB Output isn't correct
66 Incorrect 327 ms 98132 KB Output isn't correct
67 Incorrect 337 ms 102280 KB Output isn't correct
68 Incorrect 349 ms 102080 KB Output isn't correct
69 Incorrect 278 ms 81444 KB Output isn't correct
70 Incorrect 150 ms 52968 KB Output isn't correct
71 Incorrect 254 ms 74360 KB Output isn't correct
72 Incorrect 266 ms 80248 KB Output isn't correct
73 Incorrect 271 ms 80916 KB Output isn't correct
74 Incorrect 274 ms 83448 KB Output isn't correct
75 Incorrect 277 ms 83628 KB Output isn't correct
76 Incorrect 281 ms 86368 KB Output isn't correct
77 Incorrect 290 ms 86536 KB Output isn't correct
78 Incorrect 279 ms 86776 KB Output isn't correct
79 Incorrect 211 ms 58872 KB Output isn't correct
80 Incorrect 210 ms 60268 KB Output isn't correct
81 Incorrect 217 ms 60708 KB Output isn't correct
82 Incorrect 296 ms 87416 KB Output isn't correct
83 Incorrect 295 ms 89208 KB Output isn't correct
84 Incorrect 203 ms 53240 KB Output isn't correct
85 Incorrect 282 ms 88340 KB Output isn't correct
86 Incorrect 371 ms 102272 KB Output isn't correct
87 Incorrect 276 ms 87804 KB Output isn't correct
88 Incorrect 287 ms 88580 KB Output isn't correct
89 Incorrect 318 ms 97768 KB Output isn't correct
90 Incorrect 189 ms 66772 KB Output isn't correct
91 Incorrect 294 ms 92792 KB Output isn't correct
92 Incorrect 315 ms 94680 KB Output isn't correct
93 Incorrect 377 ms 101824 KB Output isn't correct
94 Incorrect 316 ms 96380 KB Output isn't correct
95 Incorrect 291 ms 90304 KB Output isn't correct
96 Incorrect 287 ms 89800 KB Output isn't correct
97 Incorrect 378 ms 102776 KB Output isn't correct
98 Incorrect 286 ms 90196 KB Output isn't correct
99 Incorrect 310 ms 96364 KB Output isn't correct
100 Incorrect 367 ms 101772 KB Output isn't correct