답안 #334435

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
334435	2020-12-09T06:56:19 Z	Kerim	Bomb (IZhO17_bomb)	C++17	100 / 100	697 ms	59500 KB

bomb

#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;
 
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N=2509;
char arr[N][N];
int up[N][N],down[N][N],ans[N];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf(" %c",&arr[i][j]);
	int h=n,w=m;		
	for(int i=1;i<=n;i++){
		int cnt=0;
		for(int j=1;j<=m;j++){
			if(arr[i][j]=='1')
				cnt++;
			else{
				if(cnt)
					w=min(w,cnt);
				cnt=0;
			}
		}
		if(cnt)
			w=min(w,cnt);
	}
	for(int j=1;j<=m;j++){
		int cnt=0;
		for(int i=1;i<=n;i++){
			if(arr[i][j]=='1')
				cnt++;
			else{
				if(cnt)
					h=min(h,cnt);
				cnt=0;	
			}	
		}
		if(cnt)
			h=min(h,cnt);
	}
	for(int j=1;j<=m;j++){
		for(int i=1;i<=n;i++)
			if(arr[i][j]=='1')
				up[i][j]=up[i-1][j]+1;
		for(int i=n;i>=1;i--)
			if(arr[i][j]=='1')
				down[i][j]=down[i+1][j]+1;	
	}
	for(int i=1;i<=w;i++)	
		ans[i]=h;	
	for(int i=1;i<=n;i++){
		int cnt=0,a=INF,b=INF;
		for(int j=1;j<=m;j++){
			if(arr[i][j]=='1'){
				umin(a,up[i][j]);
				umin(b,down[i][j]);
				umin(ans[++cnt],a+b-1);
			}
			else
				cnt=0,a=b=INF;
		}
		a=b=INF;cnt=0;
		for(int j=m;j>=1;j--){
			if(arr[i][j]=='1'){
				umin(a,up[i][j]);
				umin(b,down[i][j]);
				umin(ans[++cnt],a+b-1);
			}
			else
				cnt=0,a=b=INF;
		}
	}	
	int res=ans[1];
	for(int i=2;i<=w;i++){
		umin(ans[i],ans[i-1]);
		umax(res,i*ans[i]);
	}printf("%d\n",res);
	return 0;
}

Compilation message

bomb.cpp: In function 'int main()':
bomb.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
bomb.cpp:28:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |    scanf(" %c",&arr[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	15 ms	26476 KB	Output is correct
4	Correct	15 ms	26476 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	492 KB	Output is correct
10	Correct	1 ms	492 KB	Output is correct
11	Correct	1 ms	492 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	492 KB	Output is correct
15	Correct	1 ms	492 KB	Output is correct
16	Correct	1 ms	492 KB	Output is correct
17	Correct	1 ms	1004 KB	Output is correct
18	Correct	1 ms	748 KB	Output is correct
19	Correct	1 ms	1004 KB	Output is correct
20	Correct	1 ms	1004 KB	Output is correct
21	Correct	1 ms	620 KB	Output is correct
22	Correct	1 ms	876 KB	Output is correct
23	Correct	2 ms	1132 KB	Output is correct
24	Correct	1 ms	1004 KB	Output is correct
25	Correct	2 ms	1388 KB	Output is correct
26	Correct	2 ms	1516 KB	Output is correct
27	Correct	8 ms	4076 KB	Output is correct
28	Correct	9 ms	1516 KB	Output is correct
29	Correct	12 ms	5356 KB	Output is correct
30	Correct	15 ms	4332 KB	Output is correct
31	Correct	12 ms	3180 KB	Output is correct
32	Correct	13 ms	4204 KB	Output is correct
33	Correct	17 ms	5484 KB	Output is correct
34	Correct	7 ms	1772 KB	Output is correct
35	Correct	15 ms	2156 KB	Output is correct
36	Correct	20 ms	6892 KB	Output is correct
37	Correct	1 ms	492 KB	Output is correct
38	Correct	697 ms	59500 KB	Output is correct
39	Correct	1 ms	492 KB	Output is correct
40	Correct	86 ms	16364 KB	Output is correct
41	Correct	1 ms	492 KB	Output is correct
42	Correct	2 ms	1516 KB	Output is correct
43	Correct	638 ms	55456 KB	Output is correct
44	Correct	18 ms	6252 KB	Output is correct
45	Correct	631 ms	56684 KB	Output is correct
46	Correct	621 ms	59312 KB	Output is correct
47	Correct	636 ms	56812 KB	Output is correct
48	Correct	612 ms	59372 KB	Output is correct
49	Correct	693 ms	59244 KB	Output is correct
50	Correct	624 ms	59244 KB	Output is correct
51	Correct	614 ms	59244 KB	Output is correct
52	Correct	611 ms	59244 KB	Output is correct
53	Correct	604 ms	58604 KB	Output is correct
54	Correct	549 ms	45996 KB	Output is correct
55	Correct	545 ms	44140 KB	Output is correct
56	Correct	694 ms	59272 KB	Output is correct
57	Correct	534 ms	39404 KB	Output is correct
58	Correct	542 ms	44268 KB	Output is correct
59	Correct	580 ms	41068 KB	Output is correct
60	Correct	604 ms	51072 KB	Output is correct
61	Correct	679 ms	59372 KB	Output is correct
62	Correct	674 ms	59244 KB	Output is correct
63	Correct	672 ms	59228 KB	Output is correct
64	Correct	534 ms	42092 KB	Output is correct
65	Correct	592 ms	58348 KB	Output is correct
66	Correct	587 ms	55020 KB	Output is correct
67	Correct	596 ms	59244 KB	Output is correct
68	Correct	611 ms	59244 KB	Output is correct
69	Correct	527 ms	38764 KB	Output is correct
70	Correct	295 ms	18924 KB	Output is correct
71	Correct	511 ms	31852 KB	Output is correct
72	Correct	520 ms	37356 KB	Output is correct
73	Correct	543 ms	37740 KB	Output is correct
74	Correct	519 ms	39276 KB	Output is correct
75	Correct	522 ms	40940 KB	Output is correct
76	Correct	524 ms	42220 KB	Output is correct
77	Correct	534 ms	42860 KB	Output is correct
78	Correct	525 ms	42972 KB	Output is correct
79	Correct	464 ms	15596 KB	Output is correct
80	Correct	460 ms	16748 KB	Output is correct
81	Correct	473 ms	17132 KB	Output is correct
82	Correct	537 ms	45548 KB	Output is correct
83	Correct	533 ms	45676 KB	Output is correct
84	Correct	449 ms	10860 KB	Output is correct
85	Correct	517 ms	44652 KB	Output is correct
86	Correct	618 ms	58220 KB	Output is correct
87	Correct	512 ms	43500 KB	Output is correct
88	Correct	542 ms	44396 KB	Output is correct
89	Correct	557 ms	53228 KB	Output is correct
90	Correct	340 ms	33260 KB	Output is correct
91	Correct	576 ms	48488 KB	Output is correct
92	Correct	595 ms	50156 KB	Output is correct
93	Correct	670 ms	57452 KB	Output is correct
94	Correct	609 ms	52084 KB	Output is correct
95	Correct	560 ms	45804 KB	Output is correct
96	Correct	555 ms	45768 KB	Output is correct
97	Correct	660 ms	58220 KB	Output is correct
98	Correct	548 ms	45292 KB	Output is correct
99	Correct	570 ms	51820 KB	Output is correct
100	Correct	641 ms	56932 KB	Output is correct