#include "soccer.h"
#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
const int N = 2010;
int n;
bool a[N][N];
namespace AC {
const int N = 2010, M = 2e3 * 2e3 * 2 + 10;
int b[N], L[N], R[N], dp[M], trans[2][M];
int close[N];
vector<int> open[N], lst[N], event[2][N];
tuple<int, int, int, int> rect[M];
int solve() {
int m = 0;
auto histogram = [&] () {
stack<int> st;
for(int i = 1; i <= n; i++) {
while (!st.empty() && b[st.top()] >= b[i]) st.pop();
L[i] = st.empty() ? 0 : st.top();
st.push(i);
}
while (!st.empty()) st.pop();
for(int i = n; i >= 1; i--) {
while (!st.empty() && b[st.top()] >= b[i]) st.pop();
R[i] = st.empty() ? n + 1 : st.top();
st.push(i);
}
};
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if (a[i][j]) b[j] = 0;
else b[j]++;
}
histogram();
for(int j = 1; j <= n; j++) if (b[j]) {
rect[++m] = make_tuple(i - b[j] + 1, i, L[j] + 1, R[j] - 1);
}
}
for(int j = 1; j <= n; j++) b[j] = 0;
for(int i = n; i >= 1; i--) {
for(int j = 1; j <= n; j++) {
if (a[i][j]) b[j] = 0;
else b[j]++;
}
histogram();
for(int j = 1; j <= n; j++) if (b[j]) {
rect[++m] = make_tuple(i, i + b[j] - 1, L[j] + 1, R[j] - 1);
}
}
for(int i = 1; i <= m; i++) {
lst[get<1> (rect[i]) - get<0> (rect[i])].push_back(i);
}
for(int delta = 0; delta < n; delta++) {
for(int &i : lst[delta]) {
int x1, x2, y1, y2; tie(x1, x2, y1, y2) = rect[i];
event[0][x2].emplace_back(i);
event[1][x1].emplace_back(i);
}
}
for(int i = 1; i <= n; i++) for(int t = 0; t < 2; t++) {
for(auto &j : event[t][i]) {
int x1, x2, y1, y2; tie(x1, x2, y1, y2) = rect[j];
open[y1].push_back(j);
close[y2]++;
}
stack<int> st;
for(int j = 1; j <= n; j++) {
for(auto &k : open[j]) {
trans[t][k] = st.empty() ? 0 : st.top();
st.push(k);
} open[j].clear();
while (close[j]--) st.pop();
close[j] = 0;
}
}
int ans = 0;
for(int delta = 0; delta < n; delta++) {
for(int &i : lst[delta]) {
int x1, x2, y1, y2; tie(x1, x2, y1, y2) = rect[i];
dp[i] = (x2 - x1 + 1) * (y2 - y1 + 1);
if (trans[0][i]) { // top
int j = trans[0][i];
dp[i] = max(dp[i], dp[j] + (get<0> (rect[j]) - x1) * (y2 - y1 + 1));
} // bottom
if (trans[1][i]) {
int j = trans[1][i];
dp[i] = max(dp[i], dp[j] + (x2 - get<1> (rect[j])) * (y2 - y1 + 1));
}
ans = max(ans, dp[i]);
}
}
cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
return ans;
}
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
n = N;
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) a[i][j] = F[i][j];
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) a[i][j] = F[i - 1][j - 1];
return AC::solve();
}
#ifdef ngu
int main()
{
freopen ("task.inp", "r", stdin);
freopen ("task.out", "w", stdout);
int N;
assert(1 == scanf("%d", &N));
std::vector<std::vector<int>> F(N, std::vector<int>(N));
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
assert(1 == scanf("%d", &F[i][j]));
}
}
fclose(stdin);
int res = biggest_stadium(N, F);
printf("%d\n", res);
fclose(stdout);
return 0;
}
#endif // ngu
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
10584 KB |
ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
10588 KB |
ok |
2 |
Correct |
2 ms |
10584 KB |
ok |
3 |
Correct |
2 ms |
10588 KB |
ok |
4 |
Correct |
2 ms |
10588 KB |
ok |
5 |
Correct |
2 ms |
10588 KB |
ok |
6 |
Correct |
1 ms |
10588 KB |
ok |
7 |
Correct |
4 ms |
13404 KB |
ok |
8 |
Correct |
46 ms |
37372 KB |
ok |
9 |
Correct |
734 ms |
385744 KB |
ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
10588 KB |
ok |
2 |
Correct |
2 ms |
10584 KB |
ok |
3 |
Correct |
1 ms |
10588 KB |
ok |
4 |
Correct |
2 ms |
10588 KB |
ok |
5 |
Correct |
1 ms |
10588 KB |
ok |
6 |
Correct |
3 ms |
10584 KB |
ok |
7 |
Correct |
1 ms |
10588 KB |
ok |
8 |
Correct |
2 ms |
10584 KB |
ok |
9 |
Correct |
1 ms |
10588 KB |
ok |
10 |
Correct |
1 ms |
10588 KB |
ok |
11 |
Correct |
2 ms |
10588 KB |
ok |
12 |
Correct |
2 ms |
10588 KB |
ok |
13 |
Correct |
1 ms |
10588 KB |
ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
10584 KB |
ok |
2 |
Correct |
4 ms |
10588 KB |
ok |
3 |
Correct |
2 ms |
10584 KB |
ok |
4 |
Correct |
1 ms |
10588 KB |
ok |
5 |
Correct |
2 ms |
10588 KB |
ok |
6 |
Correct |
1 ms |
10588 KB |
ok |
7 |
Correct |
3 ms |
10584 KB |
ok |
8 |
Correct |
1 ms |
10588 KB |
ok |
9 |
Correct |
2 ms |
10584 KB |
ok |
10 |
Correct |
1 ms |
10588 KB |
ok |
11 |
Correct |
1 ms |
10588 KB |
ok |
12 |
Correct |
2 ms |
10588 KB |
ok |
13 |
Correct |
2 ms |
10588 KB |
ok |
14 |
Correct |
1 ms |
10588 KB |
ok |
15 |
Correct |
2 ms |
10840 KB |
ok |
16 |
Correct |
2 ms |
10584 KB |
ok |
17 |
Correct |
2 ms |
10588 KB |
ok |
18 |
Correct |
2 ms |
10584 KB |
ok |
19 |
Correct |
2 ms |
10584 KB |
ok |
20 |
Correct |
2 ms |
10588 KB |
ok |
21 |
Correct |
1 ms |
10588 KB |
ok |
22 |
Correct |
2 ms |
10584 KB |
ok |
23 |
Correct |
1 ms |
10588 KB |
ok |
24 |
Correct |
2 ms |
10588 KB |
ok |
25 |
Correct |
1 ms |
10588 KB |
ok |
26 |
Correct |
2 ms |
10588 KB |
ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
10584 KB |
ok |
2 |
Correct |
4 ms |
10588 KB |
ok |
3 |
Correct |
2 ms |
10584 KB |
ok |
4 |
Correct |
2 ms |
10588 KB |
ok |
5 |
Correct |
2 ms |
10588 KB |
ok |
6 |
Correct |
1 ms |
10588 KB |
ok |
7 |
Correct |
2 ms |
10588 KB |
ok |
8 |
Correct |
1 ms |
10588 KB |
ok |
9 |
Correct |
3 ms |
10584 KB |
ok |
10 |
Correct |
1 ms |
10588 KB |
ok |
11 |
Correct |
2 ms |
10584 KB |
ok |
12 |
Correct |
1 ms |
10588 KB |
ok |
13 |
Correct |
1 ms |
10588 KB |
ok |
14 |
Correct |
2 ms |
10588 KB |
ok |
15 |
Correct |
2 ms |
10588 KB |
ok |
16 |
Correct |
1 ms |
10588 KB |
ok |
17 |
Correct |
2 ms |
10840 KB |
ok |
18 |
Correct |
2 ms |
10584 KB |
ok |
19 |
Correct |
2 ms |
10588 KB |
ok |
20 |
Correct |
2 ms |
10584 KB |
ok |
21 |
Correct |
2 ms |
10584 KB |
ok |
22 |
Correct |
2 ms |
10588 KB |
ok |
23 |
Correct |
1 ms |
10588 KB |
ok |
24 |
Correct |
2 ms |
10584 KB |
ok |
25 |
Correct |
1 ms |
10588 KB |
ok |
26 |
Correct |
2 ms |
10588 KB |
ok |
27 |
Correct |
1 ms |
10588 KB |
ok |
28 |
Correct |
2 ms |
10588 KB |
ok |
29 |
Correct |
2 ms |
10588 KB |
ok |
30 |
Correct |
2 ms |
10584 KB |
ok |
31 |
Correct |
2 ms |
10588 KB |
ok |
32 |
Correct |
2 ms |
10588 KB |
ok |
33 |
Correct |
1 ms |
10588 KB |
ok |
34 |
Correct |
2 ms |
10588 KB |
ok |
35 |
Correct |
2 ms |
10584 KB |
ok |
36 |
Correct |
2 ms |
10588 KB |
ok |
37 |
Correct |
2 ms |
10588 KB |
ok |
38 |
Correct |
2 ms |
10588 KB |
ok |
39 |
Correct |
2 ms |
10588 KB |
ok |
40 |
Correct |
2 ms |
10588 KB |
ok |
41 |
Correct |
2 ms |
10588 KB |
ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
10584 KB |
ok |
2 |
Correct |
4 ms |
10588 KB |
ok |
3 |
Correct |
2 ms |
10584 KB |
ok |
4 |
Correct |
2 ms |
10588 KB |
ok |
5 |
Correct |
2 ms |
10588 KB |
ok |
6 |
Correct |
1 ms |
10588 KB |
ok |
7 |
Correct |
2 ms |
10588 KB |
ok |
8 |
Correct |
1 ms |
10588 KB |
ok |
9 |
Correct |
3 ms |
10584 KB |
ok |
10 |
Correct |
1 ms |
10588 KB |
ok |
11 |
Correct |
2 ms |
10584 KB |
ok |
12 |
Correct |
1 ms |
10588 KB |
ok |
13 |
Correct |
1 ms |
10588 KB |
ok |
14 |
Correct |
2 ms |
10588 KB |
ok |
15 |
Correct |
2 ms |
10588 KB |
ok |
16 |
Correct |
1 ms |
10588 KB |
ok |
17 |
Correct |
2 ms |
10840 KB |
ok |
18 |
Correct |
2 ms |
10584 KB |
ok |
19 |
Correct |
2 ms |
10588 KB |
ok |
20 |
Correct |
2 ms |
10584 KB |
ok |
21 |
Correct |
2 ms |
10584 KB |
ok |
22 |
Correct |
2 ms |
10588 KB |
ok |
23 |
Correct |
1 ms |
10588 KB |
ok |
24 |
Correct |
2 ms |
10584 KB |
ok |
25 |
Correct |
1 ms |
10588 KB |
ok |
26 |
Correct |
2 ms |
10588 KB |
ok |
27 |
Correct |
1 ms |
10588 KB |
ok |
28 |
Correct |
2 ms |
10588 KB |
ok |
29 |
Correct |
2 ms |
10588 KB |
ok |
30 |
Correct |
2 ms |
10584 KB |
ok |
31 |
Correct |
2 ms |
10588 KB |
ok |
32 |
Correct |
2 ms |
10588 KB |
ok |
33 |
Correct |
1 ms |
10588 KB |
ok |
34 |
Correct |
2 ms |
10588 KB |
ok |
35 |
Correct |
2 ms |
10584 KB |
ok |
36 |
Correct |
2 ms |
10588 KB |
ok |
37 |
Correct |
2 ms |
10588 KB |
ok |
38 |
Correct |
2 ms |
10588 KB |
ok |
39 |
Correct |
2 ms |
10588 KB |
ok |
40 |
Correct |
2 ms |
10588 KB |
ok |
41 |
Correct |
2 ms |
10588 KB |
ok |
42 |
Correct |
75 ms |
34164 KB |
ok |
43 |
Correct |
62 ms |
31424 KB |
ok |
44 |
Correct |
73 ms |
36112 KB |
ok |
45 |
Correct |
68 ms |
36440 KB |
ok |
46 |
Correct |
63 ms |
35492 KB |
ok |
47 |
Correct |
41 ms |
37432 KB |
ok |
48 |
Correct |
34 ms |
26084 KB |
ok |
49 |
Correct |
35 ms |
26448 KB |
ok |
50 |
Correct |
37 ms |
30672 KB |
ok |
51 |
Correct |
45 ms |
35024 KB |
ok |
52 |
Correct |
25 ms |
18512 KB |
ok |
53 |
Correct |
23 ms |
17464 KB |
ok |
54 |
Correct |
30 ms |
18344 KB |
ok |
55 |
Correct |
31 ms |
19288 KB |
ok |
56 |
Correct |
29 ms |
22600 KB |
ok |
57 |
Correct |
49 ms |
37060 KB |
ok |
58 |
Correct |
52 ms |
37144 KB |
ok |
59 |
Correct |
51 ms |
37596 KB |
ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
10584 KB |
ok |
2 |
Correct |
4 ms |
10588 KB |
ok |
3 |
Correct |
2 ms |
10584 KB |
ok |
4 |
Correct |
2 ms |
10588 KB |
ok |
5 |
Correct |
2 ms |
10588 KB |
ok |
6 |
Correct |
2 ms |
10588 KB |
ok |
7 |
Correct |
1 ms |
10588 KB |
ok |
8 |
Correct |
4 ms |
13404 KB |
ok |
9 |
Correct |
46 ms |
37372 KB |
ok |
10 |
Correct |
734 ms |
385744 KB |
ok |
11 |
Correct |
1 ms |
10588 KB |
ok |
12 |
Correct |
2 ms |
10588 KB |
ok |
13 |
Correct |
1 ms |
10588 KB |
ok |
14 |
Correct |
3 ms |
10584 KB |
ok |
15 |
Correct |
1 ms |
10588 KB |
ok |
16 |
Correct |
2 ms |
10584 KB |
ok |
17 |
Correct |
1 ms |
10588 KB |
ok |
18 |
Correct |
1 ms |
10588 KB |
ok |
19 |
Correct |
2 ms |
10588 KB |
ok |
20 |
Correct |
2 ms |
10588 KB |
ok |
21 |
Correct |
1 ms |
10588 KB |
ok |
22 |
Correct |
2 ms |
10840 KB |
ok |
23 |
Correct |
2 ms |
10584 KB |
ok |
24 |
Correct |
2 ms |
10588 KB |
ok |
25 |
Correct |
2 ms |
10584 KB |
ok |
26 |
Correct |
2 ms |
10584 KB |
ok |
27 |
Correct |
2 ms |
10588 KB |
ok |
28 |
Correct |
1 ms |
10588 KB |
ok |
29 |
Correct |
2 ms |
10584 KB |
ok |
30 |
Correct |
1 ms |
10588 KB |
ok |
31 |
Correct |
2 ms |
10588 KB |
ok |
32 |
Correct |
1 ms |
10588 KB |
ok |
33 |
Correct |
2 ms |
10588 KB |
ok |
34 |
Correct |
2 ms |
10588 KB |
ok |
35 |
Correct |
2 ms |
10584 KB |
ok |
36 |
Correct |
2 ms |
10588 KB |
ok |
37 |
Correct |
2 ms |
10588 KB |
ok |
38 |
Correct |
1 ms |
10588 KB |
ok |
39 |
Correct |
2 ms |
10588 KB |
ok |
40 |
Correct |
2 ms |
10584 KB |
ok |
41 |
Correct |
2 ms |
10588 KB |
ok |
42 |
Correct |
2 ms |
10588 KB |
ok |
43 |
Correct |
2 ms |
10588 KB |
ok |
44 |
Correct |
2 ms |
10588 KB |
ok |
45 |
Correct |
2 ms |
10588 KB |
ok |
46 |
Correct |
2 ms |
10588 KB |
ok |
47 |
Correct |
75 ms |
34164 KB |
ok |
48 |
Correct |
62 ms |
31424 KB |
ok |
49 |
Correct |
73 ms |
36112 KB |
ok |
50 |
Correct |
68 ms |
36440 KB |
ok |
51 |
Correct |
63 ms |
35492 KB |
ok |
52 |
Correct |
41 ms |
37432 KB |
ok |
53 |
Correct |
34 ms |
26084 KB |
ok |
54 |
Correct |
35 ms |
26448 KB |
ok |
55 |
Correct |
37 ms |
30672 KB |
ok |
56 |
Correct |
45 ms |
35024 KB |
ok |
57 |
Correct |
25 ms |
18512 KB |
ok |
58 |
Correct |
23 ms |
17464 KB |
ok |
59 |
Correct |
30 ms |
18344 KB |
ok |
60 |
Correct |
31 ms |
19288 KB |
ok |
61 |
Correct |
29 ms |
22600 KB |
ok |
62 |
Correct |
49 ms |
37060 KB |
ok |
63 |
Correct |
52 ms |
37144 KB |
ok |
64 |
Correct |
51 ms |
37596 KB |
ok |
65 |
Correct |
1438 ms |
346396 KB |
ok |
66 |
Correct |
589 ms |
154052 KB |
ok |
67 |
Correct |
390 ms |
79816 KB |
ok |
68 |
Correct |
1560 ms |
390628 KB |
ok |
69 |
Correct |
2069 ms |
380804 KB |
ok |
70 |
Correct |
1931 ms |
376512 KB |
ok |
71 |
Correct |
1328 ms |
392952 KB |
ok |
72 |
Correct |
645 ms |
384472 KB |
ok |
73 |
Correct |
709 ms |
228140 KB |
ok |
74 |
Correct |
738 ms |
234792 KB |
ok |
75 |
Correct |
727 ms |
231604 KB |
ok |
76 |
Correct |
586 ms |
297620 KB |
ok |
77 |
Correct |
555 ms |
297708 KB |
ok |
78 |
Correct |
964 ms |
375972 KB |
ok |
79 |
Correct |
364 ms |
65472 KB |
ok |
80 |
Correct |
360 ms |
65432 KB |
ok |
81 |
Correct |
441 ms |
85896 KB |
ok |
82 |
Correct |
637 ms |
136388 KB |
ok |
83 |
Correct |
504 ms |
115580 KB |
ok |
84 |
Correct |
394 ms |
79292 KB |
ok |
85 |
Correct |
375 ms |
68552 KB |
ok |
86 |
Correct |
400 ms |
98348 KB |
ok |
87 |
Correct |
430 ms |
100184 KB |
ok |
88 |
Correct |
476 ms |
195772 KB |
ok |
89 |
Correct |
654 ms |
377900 KB |
ok |
90 |
Correct |
617 ms |
311076 KB |
ok |
91 |
Correct |
714 ms |
354496 KB |
ok |
92 |
Correct |
419 ms |
89232 KB |
ok |
93 |
Correct |
426 ms |
82736 KB |
ok |
94 |
Correct |
395 ms |
72392 KB |
ok |
95 |
Correct |
347 ms |
77312 KB |
ok |
96 |
Correct |
368 ms |
76984 KB |
ok |
97 |
Correct |
414 ms |
76940 KB |
ok |
98 |
Correct |
381 ms |
60548 KB |
ok |
99 |
Correct |
905 ms |
362648 KB |
ok |
100 |
Correct |
998 ms |
408184 KB |
ok |
101 |
Correct |
1057 ms |
414596 KB |
ok |
102 |
Correct |
1144 ms |
407264 KB |
ok |
103 |
Correct |
1096 ms |
409060 KB |
ok |
104 |
Correct |
1117 ms |
409832 KB |
ok |
105 |
Correct |
1098 ms |
408636 KB |
ok |
106 |
Correct |
1060 ms |
415124 KB |
ok |
107 |
Correct |
1070 ms |
415888 KB |
ok |
108 |
Correct |
690 ms |
330420 KB |
ok |
109 |
Correct |
754 ms |
330544 KB |
ok |