# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
169628 |
2019-12-21T16:58:14 Z |
davitmarg |
Bomb (IZhO17_bomb) |
C++17 |
|
1000 ms |
98616 KB |
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;
const int N = 2505;
int n, m, a[N][N], pr[N][N], lst[N][N], nxt[N][N];
char x;
int ans = 1;
void add(int sy, int sx, int y, int x)
{
pr[sy][sx]++;
pr[y][x]++;
pr[sy][x]--;
pr[y][sx]--;
}
int get(int sy, int sx, int y, int x)
{
return a[y][x] - a[sy - 1][x] - a[y][sx - 1] + a[sy - 1][sx - 1];
}
bool check(int k, int q)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
pr[i][j] = 0;
for (int i = 1; i + k - 1 <= n; i++)
for (int j = 1; j + q - 1 <= m; j++)
if (get(i, j, i + k - 1, j + q - 1) == k * q)
add(i, j, i + k, j + q);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
pr[i][j] += pr[i - 1][j] + pr[i][j - 1] - pr[i - 1][j - 1];
if (get(i, j, i, j) != (bool)(pr[i][j]))
return 0;
}
return 1;
}
void solve(int k)
{
int l = max(ans / k, 1), r = m, mid;
while (l <= r)
{
mid = (l + r) / 2;
if (check(k, mid))
{
if (k * mid >= ans)
ans = k * mid;
l = mid + 1;
}
else
r = mid - 1;
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
scanf(" %c", &x);
a[i][j] += (x - '0');
a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (get(i, j, i, j))
lst[i][j] = 1 + lst[i - 1][j];
int len = n;
for (int i = n; i >= 1; i--)
for (int j = m; j >= 1; j--)
if (get(i, j, i, j))
{
nxt[i][j] = 1 + nxt[i + 1][j];
len = min(len, nxt[i][j] + lst[i][j] - 1);
}
if (n <= 450)
for (int i = 1; i <= len; i++)
solve(i);
else
{
for (int i = 1; i <= len; i++)
if (rand() % 40 == 0)
solve(i);
solve(len);
}
cout << ans << endl;
return 0;
}
/*
6 6
000111
000111
001111
111100
111000
111000
*/
Compilation message
bomb.cpp: In function 'int main()':
bomb.cpp:88:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c", &x);
~~~~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
2 ms |
632 KB |
Output is correct |
3 |
Correct |
37 ms |
40440 KB |
Output is correct |
4 |
Correct |
37 ms |
40444 KB |
Output is correct |
5 |
Correct |
3 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
632 KB |
Output is correct |
9 |
Correct |
2 ms |
632 KB |
Output is correct |
10 |
Correct |
2 ms |
632 KB |
Output is correct |
11 |
Correct |
2 ms |
632 KB |
Output is correct |
12 |
Correct |
2 ms |
632 KB |
Output is correct |
13 |
Correct |
2 ms |
504 KB |
Output is correct |
14 |
Correct |
2 ms |
632 KB |
Output is correct |
15 |
Correct |
2 ms |
632 KB |
Output is correct |
16 |
Correct |
2 ms |
632 KB |
Output is correct |
17 |
Correct |
4 ms |
1528 KB |
Output is correct |
18 |
Correct |
3 ms |
1272 KB |
Output is correct |
19 |
Correct |
6 ms |
1656 KB |
Output is correct |
20 |
Correct |
6 ms |
1660 KB |
Output is correct |
21 |
Correct |
3 ms |
888 KB |
Output is correct |
22 |
Correct |
4 ms |
1272 KB |
Output is correct |
23 |
Correct |
7 ms |
1784 KB |
Output is correct |
24 |
Correct |
5 ms |
1528 KB |
Output is correct |
25 |
Correct |
10 ms |
2040 KB |
Output is correct |
26 |
Correct |
7 ms |
2168 KB |
Output is correct |
27 |
Correct |
14 ms |
6136 KB |
Output is correct |
28 |
Correct |
29 ms |
3960 KB |
Output is correct |
29 |
Correct |
251 ms |
8252 KB |
Output is correct |
30 |
Correct |
431 ms |
8184 KB |
Output is correct |
31 |
Correct |
252 ms |
6136 KB |
Output is correct |
32 |
Correct |
402 ms |
7544 KB |
Output is correct |
33 |
Correct |
652 ms |
9336 KB |
Output is correct |
34 |
Correct |
25 ms |
4344 KB |
Output is correct |
35 |
Correct |
87 ms |
6136 KB |
Output is correct |
36 |
Correct |
416 ms |
10772 KB |
Output is correct |
37 |
Correct |
2 ms |
632 KB |
Output is correct |
38 |
Execution timed out |
1071 ms |
98340 KB |
Time limit exceeded |
39 |
Correct |
2 ms |
632 KB |
Output is correct |
40 |
Incorrect |
251 ms |
26488 KB |
Output isn't correct |
41 |
Correct |
3 ms |
632 KB |
Output is correct |
42 |
Correct |
12 ms |
2040 KB |
Output is correct |
43 |
Execution timed out |
1072 ms |
94548 KB |
Time limit exceeded |
44 |
Correct |
910 ms |
10180 KB |
Output is correct |
45 |
Execution timed out |
1074 ms |
95796 KB |
Time limit exceeded |
46 |
Correct |
639 ms |
98424 KB |
Output is correct |
47 |
Execution timed out |
1079 ms |
95988 KB |
Time limit exceeded |
48 |
Correct |
696 ms |
98544 KB |
Output is correct |
49 |
Correct |
704 ms |
98424 KB |
Output is correct |
50 |
Correct |
734 ms |
98436 KB |
Output is correct |
51 |
Correct |
807 ms |
98448 KB |
Output is correct |
52 |
Correct |
718 ms |
98604 KB |
Output is correct |
53 |
Correct |
762 ms |
97740 KB |
Output is correct |
54 |
Correct |
716 ms |
85316 KB |
Output is correct |
55 |
Correct |
779 ms |
83448 KB |
Output is correct |
56 |
Execution timed out |
1075 ms |
98552 KB |
Time limit exceeded |
57 |
Correct |
784 ms |
78664 KB |
Output is correct |
58 |
Correct |
782 ms |
83576 KB |
Output is correct |
59 |
Correct |
822 ms |
80404 KB |
Output is correct |
60 |
Correct |
689 ms |
90360 KB |
Output is correct |
61 |
Correct |
762 ms |
98464 KB |
Output is correct |
62 |
Execution timed out |
1079 ms |
98496 KB |
Time limit exceeded |
63 |
Execution timed out |
1087 ms |
98552 KB |
Time limit exceeded |
64 |
Execution timed out |
1084 ms |
81272 KB |
Time limit exceeded |
65 |
Correct |
756 ms |
97528 KB |
Output is correct |
66 |
Correct |
692 ms |
94200 KB |
Output is correct |
67 |
Correct |
807 ms |
98468 KB |
Output is correct |
68 |
Correct |
751 ms |
98616 KB |
Output is correct |
69 |
Correct |
741 ms |
78072 KB |
Output is correct |
70 |
Execution timed out |
1055 ms |
49584 KB |
Time limit exceeded |
71 |
Execution timed out |
1071 ms |
71064 KB |
Time limit exceeded |
72 |
Execution timed out |
1070 ms |
76476 KB |
Time limit exceeded |
73 |
Execution timed out |
1072 ms |
77048 KB |
Time limit exceeded |
74 |
Execution timed out |
1072 ms |
78588 KB |
Time limit exceeded |
75 |
Execution timed out |
1088 ms |
80248 KB |
Time limit exceeded |
76 |
Execution timed out |
1085 ms |
81580 KB |
Time limit exceeded |
77 |
Execution timed out |
1084 ms |
82008 KB |
Time limit exceeded |
78 |
Execution timed out |
1080 ms |
82180 KB |
Time limit exceeded |
79 |
Execution timed out |
1052 ms |
54860 KB |
Time limit exceeded |
80 |
Execution timed out |
1067 ms |
56084 KB |
Time limit exceeded |
81 |
Execution timed out |
1081 ms |
56256 KB |
Time limit exceeded |
82 |
Execution timed out |
1078 ms |
84656 KB |
Time limit exceeded |
83 |
Execution timed out |
1084 ms |
84984 KB |
Time limit exceeded |
84 |
Incorrect |
563 ms |
50184 KB |
Output isn't correct |
85 |
Execution timed out |
1080 ms |
83704 KB |
Time limit exceeded |
86 |
Incorrect |
684 ms |
97400 KB |
Output isn't correct |
87 |
Execution timed out |
1083 ms |
82680 KB |
Time limit exceeded |
88 |
Execution timed out |
1088 ms |
83836 KB |
Time limit exceeded |
89 |
Execution timed out |
1086 ms |
92252 KB |
Time limit exceeded |
90 |
Execution timed out |
1074 ms |
63864 KB |
Time limit exceeded |
91 |
Execution timed out |
1088 ms |
87548 KB |
Time limit exceeded |
92 |
Execution timed out |
1082 ms |
89152 KB |
Time limit exceeded |
93 |
Incorrect |
682 ms |
96608 KB |
Output isn't correct |
94 |
Execution timed out |
1086 ms |
91000 KB |
Time limit exceeded |
95 |
Execution timed out |
1087 ms |
84856 KB |
Time limit exceeded |
96 |
Execution timed out |
1090 ms |
84600 KB |
Time limit exceeded |
97 |
Incorrect |
673 ms |
97144 KB |
Output isn't correct |
98 |
Execution timed out |
1083 ms |
84348 KB |
Time limit exceeded |
99 |
Execution timed out |
1079 ms |
90616 KB |
Time limit exceeded |
100 |
Incorrect |
668 ms |
95996 KB |
Output isn't correct |