oj.uz

Submission #167416

# Submission time Handle Problem Language Result Execution time Memory
167416 2019-12-08T10:38:31 Z GioChkhaidze Bomb (IZhO17_bomb) C++14
41 / 100
 570 ms 121668 KB 
#include <bits/stdc++.h>
#define Tree int h,int l,int r
#define Left 2*h,l,(l+r)/2
#define Right 2*h+1,(l+r)/2+1,r
#define F first
#define S second
using namespace std;
const int N=2505;
int n,m,width=1e9,length=1e9,last,D[N][N],Dr[N][N],X,Y;
string s[N],S;
vector < pair < int , pair < int , int > > > v;
inline bool check(int x,int y) {
	for (int i=0; i<=n; i++)
		for (int j=0; j<=m; j++)
			Dr[i][j]=0;
	
	for (int i=0; i<n; i++) 
		for (int j=0; j<m; j++)
				if (D[i+x][j+y]-D[i][j+y]-D[i+x][j]+D[i][j]==0 && s[i][j]=='1') 
				   Dr[i+1][j+1]=Dr[i][j+1]+Dr[i+1][j]-Dr[i][j]+1;
					else
				   Dr[i+1][j+1]=Dr[i][j+1]+Dr[i+1][j]-Dr[i][j];
	
					 								     
	for (int i=1; i<=n; i++)
		for (int j=1; j<=m; j++) 
			if (s[i-1][j-1]=='1') {
				X=max(i-x,0),Y=max(j-y,0);
				if (Dr[i][j]-Dr[i][Y]-Dr[X][j]+Dr[X][Y]==0) return 0;
			}
	
	return 1;
}

main () {
	scanf("%d%d",&n,&m);
	getline(cin,S);
	for (int i=0; i<n; i++)  
		getline(cin,s[i]);
	
	for (int i=0; i<n; i++)
		for (int j=0; j<m; j++) 
			D[i+1][j+1]=D[i][j+1]+D[i+1][j]-D[i][j]+(s[i][j]=='0');
	
	for (int i=0; i<n; i++) {
		last=m;
		for (int j=m-1; j>=0; j--) {
			if (s[i][j]=='0' && last-1!=j) 
				if (width>last-j-1) width=last-j-1;
			if (s[i][j]=='0') last=j;
		}
		
		if (last) 
			if (last<width) width=last;
	}
	
	for (int j=0; j<m; j++) {
		last=n;
		for (int i=n-1; i>=0; i--) {
			if (s[i][j]=='0' && last-1!=i) 
				if (length>last-i-1) length=last-i-1;
			if (s[i][j]=='0') last=i;
		}
		
		if (last)
			if (last<length) length=last;
	}
	
	if (width==1e9 || length==1e9) { cout<<0<<endl; return 0; }

	if (1LL*width*length*n*m>=3e8) {
		cout<<width*length<<endl;
		return 0;
	}

	for (int i=1; i<=length; i++)
		for (int j=1; j<=width; j++)
			v.push_back({i*j,{i,j}});
			
	sort(v.begin(),v.end());
	
	for (int i=v.size()-1; i>=0; i--) {
		if (check(v[i].S.F,v[i].S.S)) {
			cout<<v[i].F<<endl;
			return 0;
		}
	}
}

Compilation message

bomb.cpp:35:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
bomb.cpp: In function 'int main()':
bomb.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~

Subtask #1
41.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 Runtime error 92 ms 41336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 80 ms 41336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 636 KB Output is correct
9 Correct 2 ms 636 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 632 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 2 ms 504 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 2 ms 508 KB Output is correct
17 Correct 3 ms 1016 KB Output is correct
18 Correct 3 ms 1016 KB Output is correct
19 Correct 10 ms 1272 KB Output is correct
20 Correct 11 ms 1272 KB Output is correct
21 Correct 3 ms 888 KB Output is correct
22 Correct 4 ms 1016 KB Output is correct
23 Correct 15 ms 1272 KB Output is correct
24 Correct 10 ms 1144 KB Output is correct
25 Correct 39 ms 1372 KB Output is correct
26 Correct 4 ms 1272 KB Output is correct
27 Correct 11 ms 3576 KB Output is correct
28 Correct 21 ms 3832 KB Output is correct
29 Incorrect 12 ms 2808 KB Output isn't correct
30 Incorrect 17 ms 3320 KB Output isn't correct
31 Incorrect 13 ms 2680 KB Output isn't correct
32 Incorrect 14 ms 2936 KB Output isn't correct
33 Incorrect 18 ms 3448 KB Output isn't correct
34 Correct 19 ms 4088 KB Output is correct
35 Incorrect 17 ms 3320 KB Output isn't correct
36 Correct 22 ms 6008 KB Output is correct
37 Correct 2 ms 632 KB Output is correct
38 Correct 431 ms 39532 KB Output is correct
39 Correct 2 ms 504 KB Output is correct
40 Incorrect 57 ms 8568 KB Output isn't correct
41 Correct 2 ms 632 KB Output is correct
42 Correct 44 ms 1396 KB Output is correct
43 Correct 429 ms 36864 KB Output is correct
44 Incorrect 18 ms 3452 KB Output isn't correct
45 Incorrect 428 ms 36984 KB Output isn't correct
46 Correct 435 ms 36820 KB Output is correct
47 Incorrect 426 ms 36984 KB Output isn't correct
48 Incorrect 437 ms 36956 KB Output isn't correct
49 Runtime error 547 ms 121668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Incorrect 428 ms 36984 KB Output isn't correct
51 Incorrect 428 ms 36856 KB Output isn't correct
52 Incorrect 428 ms 36772 KB Output isn't correct
53 Incorrect 426 ms 36856 KB Output isn't correct
54 Incorrect 427 ms 36840 KB Output isn't correct
55 Incorrect 432 ms 36992 KB Output isn't correct
56 Correct 434 ms 37112 KB Output is correct
57 Incorrect 429 ms 37112 KB Output isn't correct
58 Incorrect 455 ms 37112 KB Output isn't correct
59 Incorrect 439 ms 37020 KB Output isn't correct
60 Correct 425 ms 36972 KB Output is correct
61 Correct 425 ms 36968 KB Output is correct
62 Correct 422 ms 37088 KB Output is correct
63 Correct 435 ms 36984 KB Output is correct
64 Correct 427 ms 37012 KB Output is correct
65 Incorrect 425 ms 36984 KB Output isn't correct
66 Incorrect 452 ms 37092 KB Output isn't correct
67 Incorrect 434 ms 37252 KB Output isn't correct
68 Incorrect 427 ms 37192 KB Output isn't correct
69 Incorrect 434 ms 37112 KB Output isn't correct
70 Incorrect 282 ms 29228 KB Output isn't correct
71 Incorrect 445 ms 36812 KB Output isn't correct
72 Incorrect 444 ms 37240 KB Output isn't correct
73 Incorrect 431 ms 37004 KB Output isn't correct
74 Incorrect 443 ms 37220 KB Output isn't correct
75 Incorrect 433 ms 37112 KB Output isn't correct
76 Incorrect 425 ms 37212 KB Output isn't correct
77 Incorrect 453 ms 37152 KB Output isn't correct
78 Incorrect 426 ms 37132 KB Output isn't correct
79 Incorrect 472 ms 36972 KB Output isn't correct
80 Incorrect 429 ms 36864 KB Output isn't correct
81 Incorrect 432 ms 36908 KB Output isn't correct
82 Incorrect 430 ms 37276 KB Output isn't correct
83 Incorrect 430 ms 37144 KB Output isn't correct
84 Incorrect 433 ms 36832 KB Output isn't correct
85 Incorrect 430 ms 36932 KB Output isn't correct
86 Incorrect 430 ms 36864 KB Output isn't correct
87 Incorrect 435 ms 36916 KB Output isn't correct
88 Incorrect 432 ms 37112 KB Output isn't correct
89 Incorrect 432 ms 36808 KB Output isn't correct
90 Incorrect 276 ms 29084 KB Output isn't correct
91 Incorrect 440 ms 36896 KB Output isn't correct
92 Incorrect 570 ms 36444 KB Output isn't correct
93 Incorrect 438 ms 36368 KB Output isn't correct
94 Incorrect 427 ms 36608 KB Output isn't correct
95 Incorrect 455 ms 37240 KB Output isn't correct
96 Incorrect 427 ms 37228 KB Output isn't correct
97 Incorrect 423 ms 36728 KB Output isn't correct
98 Incorrect 426 ms 37240 KB Output isn't correct
99 Incorrect 425 ms 36600 KB Output isn't correct
100 Incorrect 423 ms 36580 KB Output isn't correct