답안 #38394 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
38394	2018-01-04T05:03:25 Z	mirbek01	Bomb (IZhO17_bomb)	C++14	41 / 100	1000 ms	32656 KB

bomb

# include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

# define pb push_back
# define fr first
# define sc second
# define mk make_pair

using namespace std;

const long long linf = 1e18 + 7;
const int inf = 1e9 + 7;
const int N = 2505;

typedef long long ll;

int n, m, a = inf, b = inf, pref[N][N];
char ch[N][N];

int get(int l, int r, int l2, int r2){
      return pref[l2][r2] - pref[l2][r - 1] - pref[l - 1][r2] + pref[l - 1][r - 1];
}

int main(){
      scanf("%d %d", &n, &m);
      int cnt = 0;
      for(int i = 1; i <= n; i ++){
            scanf("\n");
            for(int j = 1; j <= m; j ++){
                  scanf("%c", &ch[i][j]);
                  if(ch[i][j] == '1') cnt ++;
            }
      }

      if(!cnt){
            printf("0");
            return 0;
      }

      for(int i = 1; i <= n; i ++){
            int cur = 0;
            for(int j = 1; j <= m; j ++){
                  if(ch[i][j] == '1') cur ++;
                  else{
                        if(cur) a = min(a, cur);
                        cur = 0;
                  }
            }
            if(cur) a = min(a, cur);
      }

      for(int i = 1; i <= m; i ++){
            int cur = 0;
            for(int j = 1; j <= n; j ++){
                  if(ch[j][i] == '1') cur ++;
                  else {
                        if(cur) b = min(b, cur);
                        cur = 0;
                  }
            }
            if(cur) b = min(b, cur);
      }
      if(n > 100 || m > 100){
            printf("%d", a * b);
      } else {
            for(int i = 1; i <= n; i ++){
                  for(int j = 1; j <= m; j ++){
                        if(ch[i][j] == '1') pref[i][j] ++;
                        pref[i][j] += pref[i][j - 1];
                  }
            }
            for(int i = 1; i <= n; i ++)
                  for(int j = 1; j <= m; j ++)
                        pref[i][j] += pref[i - 1][j];
            int ans = 0;
            for(int x = 1; x <= n; x ++){
                  for(int y = 1; y <= m; y ++){
                        if(x * y <= ans) continue;
                        int used[101][101];
                        for(int i = 1; i <= n; i ++)
                              for(int j = 1; j <= m; j ++)
                                    used[i][j] = 0;
                        for(int i = 1; i <= n - x + 1; i ++){
                              for(int j = 1; j <= m - y + 1; j ++){
                                    int i1 = i + x - 1, j1 = j + y - 1;
                                    if(get(i, j, i1, j1) == x * y){
                                          for(int xx = i; xx <= i1; xx ++){
                                                for(int yy = j; yy <= j1; yy ++){
                                                      used[xx][yy] = 1;
                                                }
                                          }
                                    }
                              }
                        }
                        int fl = true;
                        for(int i = 1; i <= n; i ++){
                              for(int j = 1; j <= m; j ++){
                                    if(ch[i][j] == '1' && !used[i][j]) fl = false;
                              }
                        }
                        if(fl) ans = max(ans, x * y);
                  }
            }
            printf("%d", ans);
      }
}

Compilation message

bomb.cpp: In function 'int main()':
bomb.cpp:25:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &n, &m);
                             ^
bomb.cpp:28:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("\n");
                        ^
bomb.cpp:30:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                   scanf("%c", &ch[i][j]);
                                         ^

Subtask #1
41.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	32656 KB	Output is correct
2	Correct	0 ms	32656 KB	Output is correct
3	Correct	0 ms	32656 KB	Output is correct
4	Correct	0 ms	32656 KB	Output is correct
5	Correct	0 ms	32656 KB	Output is correct
6	Correct	0 ms	32656 KB	Output is correct
7	Correct	0 ms	32656 KB	Output is correct
8	Correct	0 ms	32656 KB	Output is correct
9	Correct	0 ms	32656 KB	Output is correct
10	Correct	0 ms	32656 KB	Output is correct
11	Correct	0 ms	32656 KB	Output is correct
12	Correct	0 ms	32656 KB	Output is correct
13	Correct	0 ms	32656 KB	Output is correct
14	Correct	0 ms	32656 KB	Output is correct
15	Correct	0 ms	32656 KB	Output is correct
16	Correct	0 ms	32656 KB	Output is correct
17	Correct	49 ms	32656 KB	Output is correct
18	Correct	66 ms	32656 KB	Output is correct
19	Correct	163 ms	32656 KB	Output is correct
20	Correct	129 ms	32656 KB	Output is correct
21	Correct	43 ms	32656 KB	Output is correct
22	Correct	103 ms	32656 KB	Output is correct
23	Correct	236 ms	32656 KB	Output is correct
24	Correct	86 ms	32656 KB	Output is correct
25	Correct	269 ms	32656 KB	Output is correct
26	Execution timed out	1000 ms	32656 KB	Execution timed out
27	Correct	6 ms	32656 KB	Output is correct
28	Incorrect	0 ms	32656 KB	Output isn't correct
29	Incorrect	9 ms	32656 KB	Output isn't correct
30	Incorrect	9 ms	32656 KB	Output isn't correct
31	Incorrect	6 ms	32656 KB	Output isn't correct
32	Incorrect	3 ms	32656 KB	Output isn't correct
33	Incorrect	6 ms	32656 KB	Output isn't correct
34	Incorrect	3 ms	32656 KB	Output isn't correct
35	Incorrect	9 ms	32656 KB	Output isn't correct
36	Correct	13 ms	32656 KB	Output is correct
37	Correct	0 ms	32656 KB	Output is correct
38	Correct	369 ms	32656 KB	Output is correct
39	Correct	0 ms	32656 KB	Output is correct
40	Incorrect	43 ms	32656 KB	Output isn't correct
41	Correct	0 ms	32656 KB	Output is correct
42	Correct	496 ms	32656 KB	Output is correct
43	Correct	343 ms	32656 KB	Output is correct
44	Incorrect	13 ms	32656 KB	Output isn't correct
45	Incorrect	316 ms	32656 KB	Output isn't correct
46	Correct	486 ms	32656 KB	Output is correct
47	Incorrect	403 ms	32656 KB	Output isn't correct
48	Incorrect	356 ms	32656 KB	Output isn't correct
49	Correct	409 ms	32656 KB	Output is correct
50	Incorrect	399 ms	32656 KB	Output isn't correct
51	Incorrect	356 ms	32656 KB	Output isn't correct
52	Incorrect	373 ms	32656 KB	Output isn't correct
53	Incorrect	366 ms	32656 KB	Output isn't correct
54	Incorrect	383 ms	32656 KB	Output isn't correct
55	Incorrect	363 ms	32656 KB	Output isn't correct
56	Correct	313 ms	32656 KB	Output is correct
57	Incorrect	349 ms	32656 KB	Output isn't correct
58	Incorrect	336 ms	32656 KB	Output isn't correct
59	Incorrect	419 ms	32656 KB	Output isn't correct
60	Correct	389 ms	32656 KB	Output is correct
61	Correct	343 ms	32656 KB	Output is correct
62	Correct	343 ms	32656 KB	Output is correct
63	Correct	299 ms	32656 KB	Output is correct
64	Correct	323 ms	32656 KB	Output is correct
65	Incorrect	363 ms	32656 KB	Output isn't correct
66	Incorrect	376 ms	32656 KB	Output isn't correct
67	Incorrect	343 ms	32656 KB	Output isn't correct
68	Incorrect	376 ms	32656 KB	Output isn't correct
69	Incorrect	319 ms	32656 KB	Output isn't correct
70	Incorrect	246 ms	32656 KB	Output isn't correct
71	Incorrect	319 ms	32656 KB	Output isn't correct
72	Incorrect	349 ms	32656 KB	Output isn't correct
73	Incorrect	376 ms	32656 KB	Output isn't correct
74	Incorrect	309 ms	32656 KB	Output isn't correct
75	Incorrect	343 ms	32656 KB	Output isn't correct
76	Incorrect	349 ms	32656 KB	Output isn't correct
77	Incorrect	399 ms	32656 KB	Output isn't correct
78	Incorrect	349 ms	32656 KB	Output isn't correct
79	Incorrect	353 ms	32656 KB	Output isn't correct
80	Incorrect	389 ms	32656 KB	Output isn't correct
81	Incorrect	413 ms	32656 KB	Output isn't correct
82	Incorrect	406 ms	32656 KB	Output isn't correct
83	Incorrect	359 ms	32656 KB	Output isn't correct
84	Incorrect	356 ms	32656 KB	Output isn't correct
85	Incorrect	413 ms	32656 KB	Output isn't correct
86	Incorrect	373 ms	32656 KB	Output isn't correct
87	Incorrect	353 ms	32656 KB	Output isn't correct
88	Incorrect	386 ms	32656 KB	Output isn't correct
89	Incorrect	366 ms	32656 KB	Output isn't correct
90	Incorrect	226 ms	32656 KB	Output isn't correct
91	Incorrect	389 ms	32656 KB	Output isn't correct
92	Incorrect	393 ms	32656 KB	Output isn't correct
93	Incorrect	379 ms	32656 KB	Output isn't correct
94	Incorrect	476 ms	32656 KB	Output isn't correct
95	Incorrect	436 ms	32656 KB	Output isn't correct
96	Incorrect	376 ms	32656 KB	Output isn't correct
97	Incorrect	356 ms	32656 KB	Output isn't correct
98	Incorrect	393 ms	32656 KB	Output isn't correct
99	Incorrect	369 ms	32656 KB	Output isn't correct
100	Incorrect	403 ms	32656 KB	Output isn't correct

답안 #38394

Compilation message

Subtask #1 41.0 / 100.0

Subtask #1
41.0 / 100.0