// correct/n3_hist.cpp
#include "soccer.h"
#include <iostream>
#include <array>
#include <map>
#include <algorithm>
#include <cassert>
const int MAXN = 3202;
class solver
{
int N;
std::vector<std::vector<int>> C;
int nxt[2][MAXN][MAXN], prv[2][MAXN][MAXN];
int up[MAXN][MAXN], down[MAXN][MAXN];
std::vector<std::array<int, 4>> rects;
std::map<std::array<int, 4>, int> rect_to_ind;
std::vector<int> dp;
void gen_max_rectangles()
{
for (int i = 0; i < N; i++)
{
std::vector<std::array<int, 3>> stack; // (start, w, h)
for (int j = 0; j <= N; j++)
{
int curr_h = j < N ? up[i][j] : 0;
int curr_start = j, curr_w = 1;
while (!stack.empty() && stack.back()[2] >= curr_h)
{
auto [start, w, h] = stack.back();
if (h > 0)
{
rects.push_back({i - h + 1, start, i, start + w - 1 + curr_w - 1});
rect_to_ind[rects.back()] = (int)rects.size() - 1;
}
curr_start = start;
curr_w += w;
stack.pop_back();
}
stack.push_back({curr_start, curr_w, curr_h});
}
}
dp.assign(rects.size(), -1);
}
void init()
{
for (int i = 0; i < N; i++)
{
nxt[0][i][N - 1] = nxt[1][i][N - 1] = N;
for (int j = N - 2; j >= 0; j--)
{
int nxt_elem = C[i][j + 1];
nxt[nxt_elem][i][j] = j + 1;
nxt[1 - nxt_elem][i][j] = nxt[1 - nxt_elem][i][j + 1];
}
prv[0][i][0] = prv[1][i][0] = -1;
for (int j = 1; j < N; j++)
{
int prv_elem = C[i][j - 1];
prv[prv_elem][i][j] = j - 1;
prv[1 - prv_elem][i][j] = prv[1 - prv_elem][i][j - 1];
}
for (int j = 0; j < N; j++)
{
up[i][j] = (C[i][j] == 1 || i == 0) ? 1 - C[i][j] : 1 + up[i - 1][j];
down[N - i - 1][j] = (C[N - i - 1][j] == 1 || i == 0) ? 1 - C[N - i - 1][j] : 1 + down[N - i][j];
}
}
}
int query_up(int row, int l, int r)
{
return *std::min_element(up[row] + l, up[row] + r + 1);
}
int query_down(int row, int l, int r)
{
return *std::min_element(down[row] + l, down[row] + r + 1);
}
int calc(int ind)
{
if (dp[ind] != -1)
return dp[ind];
int a = rects[ind][0],
b = rects[ind][1],
c = rects[ind][2],
d = rects[ind][3];
int area = (c - a + 1) * (d - b + 1);
int ans = area;
if (a > 0)
{
int start = 0 == C[a - 1][b] ? b : nxt[0][a - 1][b];
for (int i = start; i <= d;)
{
int until = std::min(nxt[1][a - 1][i] - 1, d);
if (i == b && until == d)
break;
// rmq
int x = a - 1 - query_up(a - 1, i, until) + 1;
int y = a - 1 + query_down(a - 1, i, until) - 1;
if (rect_to_ind.count({x, i, y, until}))
{
int to = rect_to_ind[{x, i, y, until}];
ans = std::max(ans, area + calc(to) - (c - a + 1) * (until - i + 1));
}
i = nxt[0][a - 1][until];
}
}
if (c + 1 < N)
{
int start = 0 == C[c + 1][b] ? b : nxt[0][c + 1][b];
for (int i = start; i <= d;)
{
int until = std::min(nxt[1][c + 1][i] - 1, d);
if (i == b && until == d)
break;
// rmq
int x = c + 1 - query_up(c + 1, i, until) + 1;
int y = c + 1 + query_down(c + 1, i, until) - 1;
if (rect_to_ind.count({x, i, y, until}))
{
int to = rect_to_ind[{x, i, y, until}];
ans = std::max(ans, area + calc(to) - (c - a + 1) * (until - i + 1));
}
i = nxt[0][c + 1][until];
}
}
return dp[ind] = ans;
}
public:
solver(int N, std::vector<std::vector<int>> C) : N(N), C(std::move(C))
{
init();
gen_max_rectangles();
}
int solve()
{
int ans = 0;
for (int i = 0; i < (int)rects.size(); i++)
{
ans = std::max(ans, calc(i));
}
return ans;
}
};
int biggest_stadium(int N, std::vector<std::vector<int>> C)
{
solver s(N, C);
return s.solve();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
79 ms |
240980 KB |
ok |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
96 ms |
240988 KB |
ok |
2 |
Correct |
101 ms |
240980 KB |
ok |
3 |
Correct |
95 ms |
241036 KB |
ok |
4 |
Correct |
114 ms |
240972 KB |
ok |
5 |
Correct |
108 ms |
240988 KB |
ok |
6 |
Correct |
112 ms |
241084 KB |
ok |
7 |
Correct |
128 ms |
241904 KB |
ok |
8 |
Correct |
178 ms |
264576 KB |
ok |
9 |
Correct |
1725 ms |
616912 KB |
ok |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
96 ms |
240988 KB |
ok |
2 |
Correct |
101 ms |
240980 KB |
ok |
3 |
Correct |
105 ms |
240960 KB |
ok |
4 |
Correct |
75 ms |
240992 KB |
ok |
5 |
Correct |
73 ms |
240948 KB |
ok |
6 |
Correct |
93 ms |
241036 KB |
ok |
7 |
Correct |
73 ms |
240924 KB |
ok |
8 |
Correct |
80 ms |
240996 KB |
ok |
9 |
Correct |
76 ms |
240972 KB |
ok |
10 |
Correct |
79 ms |
240932 KB |
ok |
11 |
Correct |
78 ms |
240972 KB |
ok |
12 |
Correct |
85 ms |
240940 KB |
ok |
13 |
Correct |
94 ms |
240972 KB |
ok |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
79 ms |
240980 KB |
ok |
2 |
Correct |
96 ms |
240988 KB |
ok |
3 |
Correct |
101 ms |
240980 KB |
ok |
4 |
Correct |
105 ms |
240960 KB |
ok |
5 |
Correct |
75 ms |
240992 KB |
ok |
6 |
Correct |
73 ms |
240948 KB |
ok |
7 |
Correct |
93 ms |
241036 KB |
ok |
8 |
Correct |
73 ms |
240924 KB |
ok |
9 |
Correct |
80 ms |
240996 KB |
ok |
10 |
Correct |
76 ms |
240972 KB |
ok |
11 |
Correct |
79 ms |
240932 KB |
ok |
12 |
Correct |
78 ms |
240972 KB |
ok |
13 |
Correct |
85 ms |
240940 KB |
ok |
14 |
Correct |
94 ms |
240972 KB |
ok |
15 |
Correct |
85 ms |
241012 KB |
ok |
16 |
Correct |
84 ms |
241036 KB |
ok |
17 |
Correct |
74 ms |
240996 KB |
ok |
18 |
Correct |
118 ms |
241052 KB |
ok |
19 |
Correct |
109 ms |
241016 KB |
ok |
20 |
Correct |
100 ms |
240984 KB |
ok |
21 |
Correct |
92 ms |
240980 KB |
ok |
22 |
Correct |
89 ms |
240960 KB |
ok |
23 |
Correct |
103 ms |
241032 KB |
ok |
24 |
Correct |
101 ms |
241036 KB |
ok |
25 |
Correct |
110 ms |
241024 KB |
ok |
26 |
Correct |
98 ms |
241012 KB |
ok |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
79 ms |
240980 KB |
ok |
2 |
Correct |
96 ms |
240988 KB |
ok |
3 |
Correct |
101 ms |
240980 KB |
ok |
4 |
Correct |
95 ms |
241036 KB |
ok |
5 |
Correct |
114 ms |
240972 KB |
ok |
6 |
Correct |
105 ms |
240960 KB |
ok |
7 |
Correct |
75 ms |
240992 KB |
ok |
8 |
Correct |
73 ms |
240948 KB |
ok |
9 |
Correct |
93 ms |
241036 KB |
ok |
10 |
Correct |
73 ms |
240924 KB |
ok |
11 |
Correct |
80 ms |
240996 KB |
ok |
12 |
Correct |
76 ms |
240972 KB |
ok |
13 |
Correct |
79 ms |
240932 KB |
ok |
14 |
Correct |
78 ms |
240972 KB |
ok |
15 |
Correct |
85 ms |
240940 KB |
ok |
16 |
Correct |
94 ms |
240972 KB |
ok |
17 |
Correct |
85 ms |
241012 KB |
ok |
18 |
Correct |
84 ms |
241036 KB |
ok |
19 |
Correct |
74 ms |
240996 KB |
ok |
20 |
Correct |
118 ms |
241052 KB |
ok |
21 |
Correct |
109 ms |
241016 KB |
ok |
22 |
Correct |
100 ms |
240984 KB |
ok |
23 |
Correct |
92 ms |
240980 KB |
ok |
24 |
Correct |
89 ms |
240960 KB |
ok |
25 |
Correct |
103 ms |
241032 KB |
ok |
26 |
Correct |
101 ms |
241036 KB |
ok |
27 |
Correct |
110 ms |
241024 KB |
ok |
28 |
Correct |
98 ms |
241012 KB |
ok |
29 |
Correct |
94 ms |
240976 KB |
ok |
30 |
Correct |
99 ms |
241112 KB |
ok |
31 |
Correct |
116 ms |
241092 KB |
ok |
32 |
Correct |
99 ms |
241084 KB |
ok |
33 |
Correct |
87 ms |
240948 KB |
ok |
34 |
Correct |
90 ms |
241024 KB |
ok |
35 |
Correct |
110 ms |
240996 KB |
ok |
36 |
Correct |
101 ms |
240984 KB |
ok |
37 |
Correct |
111 ms |
241056 KB |
ok |
38 |
Correct |
95 ms |
240964 KB |
ok |
39 |
Correct |
99 ms |
241076 KB |
ok |
40 |
Correct |
94 ms |
241100 KB |
ok |
41 |
Correct |
99 ms |
241120 KB |
ok |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
79 ms |
240980 KB |
ok |
2 |
Correct |
96 ms |
240988 KB |
ok |
3 |
Correct |
101 ms |
240980 KB |
ok |
4 |
Correct |
95 ms |
241036 KB |
ok |
5 |
Correct |
114 ms |
240972 KB |
ok |
6 |
Correct |
105 ms |
240960 KB |
ok |
7 |
Correct |
75 ms |
240992 KB |
ok |
8 |
Correct |
73 ms |
240948 KB |
ok |
9 |
Correct |
93 ms |
241036 KB |
ok |
10 |
Correct |
73 ms |
240924 KB |
ok |
11 |
Correct |
80 ms |
240996 KB |
ok |
12 |
Correct |
76 ms |
240972 KB |
ok |
13 |
Correct |
79 ms |
240932 KB |
ok |
14 |
Correct |
78 ms |
240972 KB |
ok |
15 |
Correct |
85 ms |
240940 KB |
ok |
16 |
Correct |
94 ms |
240972 KB |
ok |
17 |
Correct |
85 ms |
241012 KB |
ok |
18 |
Correct |
84 ms |
241036 KB |
ok |
19 |
Correct |
74 ms |
240996 KB |
ok |
20 |
Correct |
118 ms |
241052 KB |
ok |
21 |
Correct |
109 ms |
241016 KB |
ok |
22 |
Correct |
100 ms |
240984 KB |
ok |
23 |
Correct |
92 ms |
240980 KB |
ok |
24 |
Correct |
89 ms |
240960 KB |
ok |
25 |
Correct |
103 ms |
241032 KB |
ok |
26 |
Correct |
101 ms |
241036 KB |
ok |
27 |
Correct |
110 ms |
241024 KB |
ok |
28 |
Correct |
98 ms |
241012 KB |
ok |
29 |
Correct |
94 ms |
240976 KB |
ok |
30 |
Correct |
99 ms |
241112 KB |
ok |
31 |
Correct |
116 ms |
241092 KB |
ok |
32 |
Correct |
99 ms |
241084 KB |
ok |
33 |
Correct |
87 ms |
240948 KB |
ok |
34 |
Correct |
90 ms |
241024 KB |
ok |
35 |
Correct |
110 ms |
240996 KB |
ok |
36 |
Correct |
101 ms |
240984 KB |
ok |
37 |
Correct |
111 ms |
241056 KB |
ok |
38 |
Correct |
95 ms |
240964 KB |
ok |
39 |
Correct |
99 ms |
241076 KB |
ok |
40 |
Correct |
94 ms |
241100 KB |
ok |
41 |
Correct |
99 ms |
241120 KB |
ok |
42 |
Correct |
297 ms |
262488 KB |
ok |
43 |
Correct |
257 ms |
260420 KB |
ok |
44 |
Correct |
390 ms |
264284 KB |
ok |
45 |
Correct |
369 ms |
264460 KB |
ok |
46 |
Correct |
319 ms |
263588 KB |
ok |
47 |
Correct |
165 ms |
264488 KB |
ok |
48 |
Correct |
215 ms |
254316 KB |
ok |
49 |
Correct |
197 ms |
256272 KB |
ok |
50 |
Correct |
3481 ms |
259428 KB |
ok |
51 |
Correct |
248 ms |
261788 KB |
ok |
52 |
Correct |
137 ms |
247128 KB |
ok |
53 |
Correct |
127 ms |
245160 KB |
ok |
54 |
Correct |
153 ms |
246692 KB |
ok |
55 |
Correct |
166 ms |
248512 KB |
ok |
56 |
Correct |
170 ms |
252288 KB |
ok |
57 |
Correct |
357 ms |
264584 KB |
ok |
58 |
Correct |
396 ms |
264520 KB |
ok |
59 |
Correct |
398 ms |
264592 KB |
ok |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
79 ms |
240980 KB |
ok |
2 |
Correct |
96 ms |
240988 KB |
ok |
3 |
Correct |
101 ms |
240980 KB |
ok |
4 |
Correct |
95 ms |
241036 KB |
ok |
5 |
Correct |
114 ms |
240972 KB |
ok |
6 |
Correct |
108 ms |
240988 KB |
ok |
7 |
Correct |
112 ms |
241084 KB |
ok |
8 |
Correct |
128 ms |
241904 KB |
ok |
9 |
Correct |
178 ms |
264576 KB |
ok |
10 |
Correct |
1725 ms |
616912 KB |
ok |
11 |
Correct |
105 ms |
240960 KB |
ok |
12 |
Correct |
75 ms |
240992 KB |
ok |
13 |
Correct |
73 ms |
240948 KB |
ok |
14 |
Correct |
93 ms |
241036 KB |
ok |
15 |
Correct |
73 ms |
240924 KB |
ok |
16 |
Correct |
80 ms |
240996 KB |
ok |
17 |
Correct |
76 ms |
240972 KB |
ok |
18 |
Correct |
79 ms |
240932 KB |
ok |
19 |
Correct |
78 ms |
240972 KB |
ok |
20 |
Correct |
85 ms |
240940 KB |
ok |
21 |
Correct |
94 ms |
240972 KB |
ok |
22 |
Correct |
85 ms |
241012 KB |
ok |
23 |
Correct |
84 ms |
241036 KB |
ok |
24 |
Correct |
74 ms |
240996 KB |
ok |
25 |
Correct |
118 ms |
241052 KB |
ok |
26 |
Correct |
109 ms |
241016 KB |
ok |
27 |
Correct |
100 ms |
240984 KB |
ok |
28 |
Correct |
92 ms |
240980 KB |
ok |
29 |
Correct |
89 ms |
240960 KB |
ok |
30 |
Correct |
103 ms |
241032 KB |
ok |
31 |
Correct |
101 ms |
241036 KB |
ok |
32 |
Correct |
110 ms |
241024 KB |
ok |
33 |
Correct |
98 ms |
241012 KB |
ok |
34 |
Correct |
94 ms |
240976 KB |
ok |
35 |
Correct |
99 ms |
241112 KB |
ok |
36 |
Correct |
116 ms |
241092 KB |
ok |
37 |
Correct |
99 ms |
241084 KB |
ok |
38 |
Correct |
87 ms |
240948 KB |
ok |
39 |
Correct |
90 ms |
241024 KB |
ok |
40 |
Correct |
110 ms |
240996 KB |
ok |
41 |
Correct |
101 ms |
240984 KB |
ok |
42 |
Correct |
111 ms |
241056 KB |
ok |
43 |
Correct |
95 ms |
240964 KB |
ok |
44 |
Correct |
99 ms |
241076 KB |
ok |
45 |
Correct |
94 ms |
241100 KB |
ok |
46 |
Correct |
99 ms |
241120 KB |
ok |
47 |
Correct |
297 ms |
262488 KB |
ok |
48 |
Correct |
257 ms |
260420 KB |
ok |
49 |
Correct |
390 ms |
264284 KB |
ok |
50 |
Correct |
369 ms |
264460 KB |
ok |
51 |
Correct |
319 ms |
263588 KB |
ok |
52 |
Correct |
165 ms |
264488 KB |
ok |
53 |
Correct |
215 ms |
254316 KB |
ok |
54 |
Correct |
197 ms |
256272 KB |
ok |
55 |
Correct |
3481 ms |
259428 KB |
ok |
56 |
Correct |
248 ms |
261788 KB |
ok |
57 |
Correct |
137 ms |
247128 KB |
ok |
58 |
Correct |
127 ms |
245160 KB |
ok |
59 |
Correct |
153 ms |
246692 KB |
ok |
60 |
Correct |
166 ms |
248512 KB |
ok |
61 |
Correct |
170 ms |
252288 KB |
ok |
62 |
Correct |
357 ms |
264584 KB |
ok |
63 |
Correct |
396 ms |
264520 KB |
ok |
64 |
Correct |
398 ms |
264592 KB |
ok |
65 |
Correct |
3867 ms |
584200 KB |
ok |
66 |
Correct |
894 ms |
386900 KB |
ok |
67 |
Correct |
555 ms |
321144 KB |
ok |
68 |
Execution timed out |
4580 ms |
616652 KB |
Time limit exceeded |
69 |
Halted |
0 ms |
0 KB |
- |