oj.uz

Submission #167415

# Submission time Handle Problem Language Result Execution time Memory
167415 2019-12-08T10:33:46 Z GioChkhaidze Bomb (IZhO17_bomb) C++14
33 / 100
 1000 ms 131076 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; }

	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
33.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 88 ms 41336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 87 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 504 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 3 ms 504 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 508 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 2 ms 632 KB Output is correct
16 Correct 2 ms 636 KB Output is correct
17 Correct 3 ms 996 KB Output is correct
18 Correct 3 ms 1064 KB Output is correct
19 Correct 11 ms 1272 KB Output is correct
20 Correct 11 ms 1276 KB Output is correct
21 Correct 3 ms 888 KB Output is correct
22 Correct 4 ms 1144 KB Output is correct
23 Correct 14 ms 1404 KB Output is correct
24 Correct 10 ms 1144 KB Output is correct
25 Correct 39 ms 1272 KB Output is correct
26 Correct 4 ms 1400 KB Output is correct
27 Correct 11 ms 3576 KB Output is correct
28 Correct 22 ms 3836 KB Output is correct
29 Correct 638 ms 5060 KB Output is correct
30 Execution timed out 1075 ms 6036 KB Time limit exceeded
31 Execution timed out 1075 ms 4792 KB Time limit exceeded
32 Execution timed out 1076 ms 5368 KB Time limit exceeded
33 Execution timed out 1078 ms 6388 KB Time limit exceeded
34 Correct 19 ms 4088 KB Output is correct
35 Execution timed out 1079 ms 6008 KB Time limit exceeded
36 Correct 21 ms 6136 KB Output is correct
37 Correct 2 ms 632 KB Output is correct
38 Runtime error 603 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Correct 2 ms 632 KB Output is correct
40 Execution timed out 1081 ms 16988 KB Time limit exceeded
41 Correct 2 ms 504 KB Output is correct
42 Correct 42 ms 1400 KB Output is correct
43 Runtime error 619 ms 126800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Execution timed out 1076 ms 6896 KB Time limit exceeded
45 Runtime error 780 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Runtime error 558 ms 120440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Runtime error 791 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Runtime error 550 ms 120824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
49 Runtime error 561 ms 120568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Runtime error 553 ms 120888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
51 Runtime error 551 ms 120824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
52 Runtime error 551 ms 120900 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Runtime error 627 ms 120852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
54 Runtime error 551 ms 120716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
55 Runtime error 573 ms 120760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
56 Runtime error 550 ms 123668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
57 Runtime error 555 ms 120696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
58 Runtime error 577 ms 120888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
59 Runtime error 553 ms 120952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
60 Runtime error 553 ms 120440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
61 Runtime error 550 ms 120496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
62 Runtime error 562 ms 123500 KB Execution killed with signal 11 (could be triggered by violating memory limits)
63 Runtime error 772 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
64 Runtime error 641 ms 122300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
65 Runtime error 556 ms 120632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
66 Runtime error 551 ms 121272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
67 Runtime error 564 ms 121016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
68 Runtime error 554 ms 121200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
69 Runtime error 554 ms 120856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
70 Execution timed out 1083 ms 52880 KB Time limit exceeded
71 Runtime error 601 ms 129168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
72 Runtime error 614 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
73 Runtime error 629 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
74 Runtime error 641 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
75 Runtime error 626 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
76 Runtime error 716 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
77 Runtime error 634 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
78 Runtime error 671 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
79 Runtime error 549 ms 121080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
80 Runtime error 553 ms 120952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
81 Runtime error 583 ms 122604 KB Execution killed with signal 11 (could be triggered by violating memory limits)
82 Runtime error 640 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
83 Runtime error 641 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
84 Runtime error 555 ms 121232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
85 Runtime error 631 ms 127320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
86 Runtime error 550 ms 120888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
87 Runtime error 694 ms 126520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
88 Runtime error 642 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
89 Runtime error 561 ms 123216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
90 Execution timed out 1068 ms 53796 KB Time limit exceeded
91 Runtime error 570 ms 125580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
92 Runtime error 563 ms 124232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
93 Runtime error 563 ms 121208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
94 Runtime error 807 ms 123472 KB Execution killed with signal 11 (could be triggered by violating memory limits)
95 Runtime error 667 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
96 Runtime error 642 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
97 Runtime error 551 ms 121216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
98 Runtime error 750 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
99 Runtime error 586 ms 123464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
100 Runtime error 560 ms 121416 KB Execution killed with signal 11 (could be triggered by violating memory limits)