답안 #386486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
386486	2021-04-06T16:25:58 Z	vanic	Bomb (IZhO17_bomb)	C++14	40 / 100	1000 ms	126448 KB

bomb

#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();
		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;
			dist2[xs][ys]=dist2[p.first][p.second];
			
			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;
			dist1[xs][ys]=dist1[p.first][p.second];
			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

40.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	2 ms	492 KB	Output is correct
3	Correct	18 ms	31980 KB	Output is correct
4	Correct	18 ms	31980 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	492 KB	Output is correct
9	Correct	1 ms	620 KB	Output is correct
10	Correct	2 ms	492 KB	Output is correct
11	Correct	1 ms	620 KB	Output is correct
12	Correct	1 ms	492 KB	Output is correct
13	Correct	1 ms	492 KB	Output is correct
14	Correct	1 ms	620 KB	Output is correct
15	Correct	1 ms	620 KB	Output is correct
16	Correct	1 ms	620 KB	Output is correct
17	Incorrect	2 ms	1260 KB	Output isn't correct
18	Correct	2 ms	1004 KB	Output is correct
19	Correct	9 ms	1280 KB	Output is correct
20	Correct	9 ms	1260 KB	Output is correct
21	Correct	1 ms	748 KB	Output is correct
22	Correct	2 ms	1004 KB	Output is correct
23	Correct	13 ms	1388 KB	Output is correct
24	Correct	9 ms	1260 KB	Output is correct
25	Correct	58 ms	1644 KB	Output is correct
26	Correct	2 ms	1772 KB	Output is correct
27	Correct	6 ms	5612 KB	Output is correct
28	Correct	7 ms	2412 KB	Output is correct
29	Execution timed out	1092 ms	7332 KB	Time limit exceeded
30	Execution timed out	1096 ms	6192 KB	Time limit exceeded
31	Execution timed out	1092 ms	4656 KB	Time limit exceeded
32	Execution timed out	1086 ms	5740 KB	Time limit exceeded
33	Execution timed out	1075 ms	7404 KB	Time limit exceeded
34	Correct	6 ms	2796 KB	Output is correct
35	Correct	851 ms	3812 KB	Output is correct
36	Correct	11 ms	9644 KB	Output is correct
37	Correct	1 ms	620 KB	Output is correct
38	Execution timed out	1090 ms	124292 KB	Time limit exceeded
39	Correct	2 ms	620 KB	Output is correct
40	Execution timed out	1079 ms	22624 KB	Time limit exceeded
41	Incorrect	1 ms	620 KB	Output isn't correct
42	Incorrect	231 ms	1856 KB	Output isn't correct
43	Execution timed out	1100 ms	90908 KB	Time limit exceeded
44	Execution timed out	1084 ms	8680 KB	Time limit exceeded
45	Execution timed out	1098 ms	89508 KB	Time limit exceeded
46	Correct	303 ms	76524 KB	Output is correct
47	Execution timed out	1083 ms	89252 KB	Time limit exceeded
48	Execution timed out	1104 ms	98844 KB	Time limit exceeded
49	Correct	226 ms	126448 KB	Output is correct
50	Execution timed out	1106 ms	96944 KB	Time limit exceeded
51	Execution timed out	1094 ms	97660 KB	Time limit exceeded
52	Execution timed out	1093 ms	97972 KB	Time limit exceeded
53	Execution timed out	1057 ms	97920 KB	Time limit exceeded
54	Execution timed out	1092 ms	73668 KB	Time limit exceeded
55	Execution timed out	1100 ms	72032 KB	Time limit exceeded
56	Correct	226 ms	77024 KB	Output is correct
57	Execution timed out	1100 ms	66816 KB	Time limit exceeded
58	Execution timed out	1094 ms	71648 KB	Time limit exceeded
59	Execution timed out	1090 ms	68912 KB	Time limit exceeded
60	Correct	157 ms	91808 KB	Output is correct
61	Correct	219 ms	96672 KB	Output is correct
62	Correct	227 ms	104928 KB	Output is correct
63	Correct	494 ms	93860 KB	Output is correct
64	Correct	149 ms	59188 KB	Output is correct
65	Execution timed out	1101 ms	98432 KB	Time limit exceeded
66	Execution timed out	1104 ms	76860 KB	Time limit exceeded
67	Execution timed out	1106 ms	95152 KB	Time limit exceeded
68	Execution timed out	1102 ms	92312 KB	Time limit exceeded
69	Execution timed out	1100 ms	65680 KB	Time limit exceeded
70	Execution timed out	1095 ms	32604 KB	Time limit exceeded
71	Execution timed out	1098 ms	51920 KB	Time limit exceeded
72	Execution timed out	1053 ms	59712 KB	Time limit exceeded
73	Execution timed out	1100 ms	60768 KB	Time limit exceeded
74	Execution timed out	1094 ms	62016 KB	Time limit exceeded
75	Execution timed out	1100 ms	64064 KB	Time limit exceeded
76	Execution timed out	1098 ms	65900 KB	Time limit exceeded
77	Execution timed out	1100 ms	66624 KB	Time limit exceeded
78	Execution timed out	1098 ms	66752 KB	Time limit exceeded
79	Execution timed out	1095 ms	31468 KB	Time limit exceeded
80	Execution timed out	1086 ms	32748 KB	Time limit exceeded
81	Execution timed out	1098 ms	33764 KB	Time limit exceeded
82	Execution timed out	1104 ms	69952 KB	Time limit exceeded
83	Execution timed out	1100 ms	69952 KB	Time limit exceeded
84	Execution timed out	1099 ms	26604 KB	Time limit exceeded
85	Execution timed out	1104 ms	66000 KB	Time limit exceeded
86	Execution timed out	1105 ms	118608 KB	Time limit exceeded
87	Execution timed out	1103 ms	63836 KB	Time limit exceeded
88	Execution timed out	1103 ms	68672 KB	Time limit exceeded
89	Execution timed out	1103 ms	85696 KB	Time limit exceeded
90	Execution timed out	1100 ms	48476 KB	Time limit exceeded
91	Execution timed out	1097 ms	73368 KB	Time limit exceeded
92	Execution timed out	1102 ms	81120 KB	Time limit exceeded
93	Execution timed out	1106 ms	116428 KB	Time limit exceeded
94	Execution timed out	1083 ms	84828 KB	Time limit exceeded
95	Execution timed out	1095 ms	70080 KB	Time limit exceeded
96	Execution timed out	1094 ms	69696 KB	Time limit exceeded
97	Execution timed out	1106 ms	118844 KB	Time limit exceeded
98	Execution timed out	1094 ms	69568 KB	Time limit exceeded
99	Execution timed out	1091 ms	83212 KB	Time limit exceeded
100	Execution timed out	1102 ms	114624 KB	Time limit exceeded