oj.uz

Submission #386482

# Submission time Handle Problem Language Result Execution time Memory
386482 2021-04-06T16:18:39 Z vanic Bomb (IZhO17_bomb) C++14
8 / 100
 1000 ms 131072 KB 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <array>
#include <bitset>
#include <cassert>
 
using namespace std;
 
const int maxn=2505;
 
bitset < maxn > a[maxn];
bitset < maxn > bio[maxn];
int dist1[maxn][maxn];
int dist2[maxn][maxn];
int pref[maxn][maxn];
int uk;
int n, m;
 
bool provjeri(int x, int y){
	for(int i=0; i<n; i++){
		bio[i].reset();
	}
	int val;
	queue < pair < int, int > > q;
	int br=0;
	for(int i=0; i<=n-x; i++){
		for(int j=0; j<=m-y; j++){
			val=pref[i+x][j+y]-pref[i][j+y]-pref[i+x][j]+pref[i][j];
			if(val==x*y){
				br++;
				q.push({i, j});
				dist1[i][j]=0;
				dist2[i][j]=0;
				bio[i][j]=1;
			}
		}
	}
	pair < int, int > p;
	int xs, ys;
//	cout << "pocetak " << x << ' ' << y << endl;
	while(!q.empty()){
		p=q.front();
		q.pop();
//		cout << p.first << ' ' << p.second << endl;
		xs=p.first+1;
		ys=p.second;
		if(!bio[xs][ys] && dist1[p.first][p.second]+1<x){
			br++;
			bio[xs][ys]=1;
			dist1[xs][ys]=dist1[p.first][p.second]+1;
			q.push({xs, ys});
		}
		xs=p.first;
		ys=p.second+1;
		if(!bio[xs][ys] && dist2[p.first][p.second]+1<y){
			br++;
			bio[xs][ys]=1;
			dist2[xs][ys]=dist2[p.first][p.second]+1;
			q.push({xs, ys});
		}
	}
//	cout << br << endl;
	return br==uk;
}

vector < array < int, 3 > > svi;
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	string s;
	for(int i=0; i<n; i++){
		cin >> s;
		for(int j=0; j<m; j++){
			pref[i+1][j+1]=pref[i][j+1]+pref[i+1][j]-pref[i][j];
			if(s[j]=='1'){
				pref[i+1][j+1]++;
				uk++;
				a[i][j]=1;
			}
		}
	}
	int br=0;
	int mr=1e9, mc=1e9;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(a[i][j]){
				br++;
			}
			else if(br){
				mr=min(mr, br);
				br=0;
			}
		}
		if(br){
			mr=min(mr, br);
			br=0;
		}
	}
	for(int j=0; j<m; j++){
		for(int i=0; i<n; i++){
			if(a[i][j]){
				br++;
			}
			else if(br){
				mc=min(mc, br);
				br=0;
			}
		}
		if(br){
			mc=min(mc, br);
			br=0;
		}
	}
	assert(mr!=1e9);
	for(int i=mc; i>0; i--){
		for(int j=mr; j>0; j--){
			svi.push_back({i*j, i, j});
		}
	}
	sort(svi.begin(), svi.end());
	for(int i=svi.size()-1; i>-1; i--){
		if(provjeri(svi[i][1], svi[i][2])){
			cout << svi[i][0] << '\n';
			return 0;
		}
	}
	return 0;
}

Subtask #1
8.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 19 ms 31468 KB Output is correct
4 Correct 18 ms 30956 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Runtime error 90 ms 43884 KB Execution killed with signal 11
8 Runtime error 86 ms 45548 KB Execution killed with signal 11
9 Runtime error 86 ms 45292 KB Execution killed with signal 11
10 Runtime error 93 ms 44580 KB Execution killed with signal 11
11 Runtime error 90 ms 45164 KB Execution killed with signal 11
12 Runtime error 86 ms 44140 KB Execution killed with signal 11
13 Correct 1 ms 492 KB Output is correct
14 Runtime error 91 ms 46128 KB Execution killed with signal 11
15 Runtime error 90 ms 45164 KB Execution killed with signal 11
16 Runtime error 90 ms 45932 KB Execution killed with signal 11
17 Runtime error 100 ms 49968 KB Execution killed with signal 11
18 Runtime error 105 ms 46060 KB Execution killed with signal 11
19 Runtime error 91 ms 46060 KB Execution killed with signal 11
20 Runtime error 97 ms 46316 KB Execution killed with signal 11
21 Runtime error 88 ms 45932 KB Execution killed with signal 11
22 Runtime error 90 ms 46060 KB Execution killed with signal 11
23 Runtime error 114 ms 47596 KB Execution killed with signal 11
24 Runtime error 99 ms 46188 KB Execution killed with signal 11
25 Runtime error 96 ms 47852 KB Execution killed with signal 11
26 Runtime error 92 ms 45420 KB Execution killed with signal 11
27 Correct 6 ms 5612 KB Output is correct
28 Runtime error 97 ms 48364 KB Execution killed with signal 11
29 Runtime error 136 ms 61292 KB Execution killed with signal 11
30 Runtime error 136 ms 62128 KB Execution killed with signal 11
31 Runtime error 133 ms 58800 KB Execution killed with signal 11
32 Runtime error 121 ms 54124 KB Execution killed with signal 11
33 Runtime error 135 ms 61820 KB Execution killed with signal 11
34 Runtime error 106 ms 50240 KB Execution killed with signal 11
35 Runtime error 139 ms 63816 KB Execution killed with signal 11
36 Incorrect 47 ms 27288 KB Output isn't correct
37 Runtime error 108 ms 45420 KB Execution killed with signal 11
38 Execution timed out 1089 ms 124268 KB Time limit exceeded
39 Runtime error 85 ms 44908 KB Execution killed with signal 11
40 Runtime error 209 ms 98144 KB Execution killed with signal 11
41 Runtime error 95 ms 45292 KB Execution killed with signal 11
42 Runtime error 95 ms 47852 KB Execution killed with signal 11
43 Execution timed out 1096 ms 94360 KB Time limit exceeded
44 Runtime error 131 ms 63208 KB Execution killed with signal 11
45 Runtime error 514 ms 131072 KB Execution killed with signal 11
46 Runtime error 490 ms 131072 KB Execution killed with signal 11
47 Runtime error 501 ms 131072 KB Execution killed with signal 11
48 Execution timed out 1107 ms 98784 KB Time limit exceeded
49 Incorrect 342 ms 127080 KB Output isn't correct
50 Execution timed out 1107 ms 97072 KB Time limit exceeded
51 Execution timed out 1108 ms 97152 KB Time limit exceeded
52 Execution timed out 1105 ms 97668 KB Time limit exceeded
53 Execution timed out 1107 ms 98416 KB Time limit exceeded
54 Runtime error 425 ms 131072 KB Execution killed with signal 11
55 Runtime error 345 ms 131072 KB Execution killed with signal 6
56 Runtime error 352 ms 131072 KB Execution killed with signal 11
57 Execution timed out 1106 ms 80368 KB Time limit exceeded
58 Runtime error 406 ms 131072 KB Execution killed with signal 11
59 Runtime error 276 ms 131072 KB Execution killed with signal 11
60 Incorrect 228 ms 91848 KB Output isn't correct
61 Incorrect 341 ms 97804 KB Output isn't correct
62 Incorrect 401 ms 100620 KB Output isn't correct
63 Runtime error 650 ms 131072 KB Execution killed with signal 11
64 Runtime error 266 ms 113380 KB Execution killed with signal 11
65 Execution timed out 1097 ms 99100 KB Time limit exceeded
66 Execution timed out 1100 ms 80696 KB Time limit exceeded
67 Execution timed out 1103 ms 95280 KB Time limit exceeded
68 Execution timed out 1100 ms 92504 KB Time limit exceeded
69 Runtime error 332 ms 131072 KB Execution killed with signal 11
70 Runtime error 232 ms 116060 KB Execution killed with signal 11
71 Runtime error 311 ms 131024 KB Execution killed with signal 11
72 Runtime error 375 ms 131072 KB Execution killed with signal 11
73 Runtime error 380 ms 131072 KB Execution killed with signal 11
74 Runtime error 364 ms 131072 KB Execution killed with signal 11
75 Runtime error 361 ms 131072 KB Execution killed with signal 11
76 Runtime error 355 ms 131072 KB Execution killed with signal 11
77 Runtime error 377 ms 131072 KB Execution killed with signal 11
78 Runtime error 360 ms 131072 KB Execution killed with signal 11
79 Runtime error 189 ms 95596 KB Execution killed with signal 11
80 Runtime error 184 ms 95468 KB Execution killed with signal 11
81 Runtime error 235 ms 116580 KB Execution killed with signal 11
82 Runtime error 380 ms 131072 KB Execution killed with signal 11
83 Runtime error 353 ms 130880 KB Execution killed with signal 6
84 Runtime error 234 ms 117740 KB Execution killed with signal 11
85 Runtime error 318 ms 131072 KB Execution killed with signal 11
86 Execution timed out 1098 ms 118668 KB Time limit exceeded
87 Runtime error 289 ms 127964 KB Execution killed with signal 11
88 Runtime error 369 ms 131072 KB Execution killed with signal 11
89 Runtime error 388 ms 131072 KB Execution killed with signal 6
90 Runtime error 277 ms 118748 KB Execution killed with signal 11
91 Runtime error 340 ms 131072 KB Execution killed with signal 11
92 Runtime error 422 ms 131072 KB Execution killed with signal 11
93 Execution timed out 1087 ms 116380 KB Time limit exceeded
94 Runtime error 376 ms 131072 KB Execution killed with signal 11
95 Runtime error 371 ms 131072 KB Execution killed with signal 11
96 Runtime error 351 ms 131072 KB Execution killed with signal 11
97 Execution timed out 1097 ms 119044 KB Time limit exceeded
98 Runtime error 359 ms 131072 KB Execution killed with signal 11
99 Runtime error 367 ms 131072 KB Execution killed with signal 11
100 Execution timed out 1094 ms 114984 KB Time limit exceeded